The self descriptive number – my solution

 

I came across this video yesterday:

 

If you’re not subscribed to Dr Grime’s channel, you should be – it’s great!

I’m a bit late to the party but might as well try and solve it.

 

When I first saw the video, my thought was ‘I’ll go and write a nice programme to solve it’. Problem is, it’s not actually that difficult to solve on paper. Never mind – let’s look at how to do it on a computer. I’m using R to programme in. It is probably the worst language to use for this problem because R is designed to handle datasets – not for procedural programmes with loops. But, this makes it easier to demonstrate a couple of the issues with coming up with a solution.

Attempt 1: Brute Force

For anyone not familiar with a brute force attack, this simply involves checking a number, seeing if it satisfies the criteria. If it does, the programme ends. If it doesn’t the next number in the sequence is checked.

Brute force attacks are great because they essentially guarantee a solution to basically any (computable) problem.

On the other hand, although a solution is guaranteed, there is no upper bound on the time a brute force attack takes. Imagine running an attack on a number 100 digits long. Even if the computer could check 1 million numbers a second, it would take 10^96 seconds to check all possible numbers. This is way way longer than the age of the universe.

Still, our number is only 10 digits long, so there are about 10 billion possible solutions. That is well within the reach of a laptop.

 

Here is what my brute force script does:

Start with a number, N=1000000000

While (N!=NN){

Split the number into a vector of its digits, NI

Produce a vector of 10 digits, Ni, where digit 1 is the number of 0s in NI, digit 2 is the number of 1s in NI etc…

Collapse NI back into an integer,NN

If N=NN, break the loop. NN is the solution

}

 

Remember how I said R is not the ideal language to use for this? My laptop has been running this code for 5 hours now and still has not found a solution. Loops run really slowly in R so we need a better way of doing this.

 

Attempt 2 – an iterative approach

Rather than counting through the entire sequence of 10 digit numbers, it’s better to keep improving the output at the end of each loop until we get the solution.

In other words, we want the number, NN, to get closer to the actual solution with each loop.

Here’s what I did to achieve this:

 

Start with a number, N=1000000000

While (N!=NN){

Split the number into a vector of its digits, Ni

Select a digit, D, at random from Ni and replace it with the number of times integer S appears in Ni, where S = (position of digit D-1)

Collapse Ni back into an integer, NN

If N=NN, break the loop. NN is the solution

else N=NN

}

 

This is obviously not a perfect script as it relies on randomly selecting positions in the vector Ni. However, if we cannot (or can’t be bothered to) come up with an algorithm to find the solution quickly, this script will still find it significantly faster than a brute force attack. It is a trade off between quickly writing the script for a brute force but waiting for it to find a solution, and devising an algorithm which runs quickly (still less than a second).

Here’s how it got there:

outputs

Progress of the iterative program to find the solution. It took a total of 104 iterations. The areas where the same number turned up repeatedly are where the random number had no effect on the output as it ‘selected’ a digit which did not change.

 

By the way, the answer is 6210001000

 

Code in full

Brute force

#change number of digits by changing starting numbers and number of elements in Nb

#this will take about 15 hours to find a 10 digit solution

#Turn off scientific notation
options(scipen=999)

#declare starting conditions

N<-10000000000
NB<-9100000000

while(N!=NB){
#value of N is previous value +1
N=as.double(N+1)

#vector of digits of N
Ni<-as.numeric(strsplit(as.character(N),””)[[1]])
Nd<-c(Ni)

#create ‘referential’ vector of digits
Nb[1]<-length(which(Ni == 0))
Nb[2]<-length(which(Ni == 1))
Nb[3]<-length(which(Ni == 2))
Nb[4]<-length(which(Ni == 3))
Nb[5]<-length(which(Ni == 4))
Nb[6]<-length(which(Ni == 5))
Nb[7]<-length(which(Ni == 6))
Nb[8]<-length(which(Ni == 7))
Nb[9]<-length(which(Ni == 8))
Nb[10]<-length(which(Ni == 9))
#collapse into integer
NB<-as.numeric(paste(Nb, collapse = “”))

#stop if solution found
if(N==NB){
break}
}

Iterative

#this will find a solution almost instantly
#Turn off scientific notation
options(scipen=999)

#declare variables and starting conditions
N<-1000000000
NC<-9100000000
Nc<-c(9,1,0,0,0,0,0,0,0,0)
Nb<-c(1,0,0,0,0,0,0,0,0,0)

NN<-as.double(8200000000)

while(N!=NC){

#use double floating point due to number of sig figs
N=as.double(NN)

#split N into vector of elements
Ni<-as.numeric(strsplit(as.character(N),””)[[1]])

#random number
S<-sample(1:10,1)

#replace element S in Ni with number of digits ‘S’ in Ni
Nb[S]<-length(which(Ni == (S-1)))

#elements of referrential vector
Nc[1]<-length(which(Ni == 0))
Nc[2]<-length(which(Ni == 1))
Nc[3]<-length(which(Ni == 2))
Nc[4]<-length(which(Ni == 3))
Nc[5]<-length(which(Ni == 4))
Nc[6]<-length(which(Ni == 5))
Nc[7]<-length(which(Ni == 6))
Nc[8]<-length(which(Ni == 7))
Nc[9]<-length(which(Ni == 8))
Nc[10]<-length(which(Ni == 9))

#referential vector
NC<-as.double(paste(Nc, collapse = “”))

#Output of loop
NB<-as.double(paste(Nb, collapse = “”))
NN<-NB

#Check referential vector against input
if(N==NC){

break}
}

 

 

Advertisements

One thought on “The self descriptive number – my solution

  1. Pingback: How to build a supercomputer – part 1 | brain -> blueprint -> build

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s