Solution to my April 2016 Puzzle

var css=document.createElement('style');
css.type='text/css';
css.innerHTML='.detectedPrime {background-color: red;} .sequenceMember {background-color: blue} .selected {background-color: yellow}';
document.getElementsByTagName('head')[0].appendChild(css);
var ele,eles,pele,ref,prime,sno, nums = {},ks =[],primes=[],neighbours=[],selecs=[],neighbours=[],identifiedPairs=[];


// Check whether a number is a prime
function checkNumPrime(n){

      // Check whether the number is 1,2 or 3
      if (n<4){
	  return true;
      }

      // Check the number isn't directly divisible by 2 or 3
      if (n%2 == 0 || n%3 == 0){
	  return false;
      }

      var di=2;
      var i = 5;

      // Don't calculcate higher than the square root (rounded down if needed)
      var lim = Math.floor(Math.sqrt(n));

      while (i < lim){

	if (n%i == 0){
	    return false;
	}
	i=i+di;
	di=6-di;
      }

      // If we haven't already returned, n is prime
      return true;

}


function decodeReference(id){
      // Remove the r
      id=id.substr(1);
      return id.split('c');
  
}


// Calculate the DOM ID of all adjacent cells
function calculateNeighbours(id){

      if (!id){
	  return [];
      }
  
      // Break the cell ID into a reference array
      var reference = decodeReference(id);

      // Calculate all adjacent neighbours by subtracting and adding to the reference
      var neighbours=[];

      // Calculate the permutations
      var incr = parseInt(reference[0])+1;
      var incc = parseInt(reference[1])+1;

      var decr = parseInt(reference[0])-1;
      var decc = parseInt(reference[1])-1;
      
      // Don't use negative numbers
      if (decr >= 0){
	    neighbours.push("r"+decr+"c"+reference[1]); // r-1,c
      }else{
	    neighbours.push(false);
      }
      
      // And don't fall off the edge of the grid
      if (incr <20){
	    neighbours.push("r"+incr+"c"+reference[1]); // r+1,c
      }else{
	    neighbours.push(false);
      }
      
      if (decc >=0){
	    neighbours.push("r"+reference[0]+"c"+decc); // r,c-1
      }else{
	    neighbours.push(false);
      }
      
      if (incc <20){
	  neighbours.push("r"+reference[0]+"c"+incc); // r,c+1
      }else{
	    neighbours.push(false);
      }
      
      return neighbours
}

// dir should be either c (column) or r (row)
function getDirectionalNeighbours(id,dir){
  
  var neighbours = calculateNeighbours(id);
  var dirneighbours = []
  
  if (dir == 'c'){
    dirneighbours.push(neighbours[0]);
    dirneighbours.push(neighbours[1]);
	
  }else{
    dirneighbours.push(neighbours[2]);
    dirneighbours.push(neighbours[3]);
  }
  
  return dirneighbours;
}


// Check Cells and identify whether they're part of a sequence
function isPartOfSequence(c1,c2,c3){
  
  if (!c1 || !c3){
      // don't fall off the end of the grid
    
      // Array is - isSequence, checked, sequenceorder, [cell references]
      return [false,false,false, [c1,c2,c3]];
  }
  
  n1 = parseInt(document.getElementById(c1).innerHTML);
  n2 = parseInt(document.getElementById(c2).innerHTML);
  n3 = parseInt(document.getElementById(c3).innerHTML);  
  
  var seq = false;
  var order = false;
  var cells = [c1,c2,c3];
  // Sequences can be ascending or descending, so we need to test both
  if (n1 + n2 == n3){
      seq = true;
      order = 'asc';
  }

  if (n1 - n2 == n3){
      seq = true;
      order = 'desc';
  }
  
  return [seq,true,order,cells];  
}


function colourSequenceMembers(ids){
  
  for (var i=0; i<ids.length;i++){
      document.getElementById(ids[i]).className = 'sequenceMember';
  }
  
}


function enforceFourWay(cells,direction){
      var dnb = getDirectionalNeighbours(cells[0],direction);
      var dseq = isPartOfSequence(dnb[0],cells[0],dnb[1]);
      var match = false;

      if (dseq[0] == true){
	  colourSequenceMembers(dseq[3]);
	  match=true;
      }

      var unb = getDirectionalNeighbours(cells[2],direction);
      var useq = isPartOfSequence(unb[0],cells[2],unb[1]);
      if (useq[0] == true){
	  colourSequenceMembers(useq[3]);
	  match=true;
      }		
      return match;
}

// Becaues Javascript is a dick when it comes to sorting numbers
function sortNumber(a,b) {
    return a - b;
}


// Cycle through cells and colour the primes as a starting point
eles = document.getElementsByTagName('td');


for (var i=0; i<eles.length; i++){
      if (checkNumPrime(eles[i].innerHTML)){
	primes.push(eles[i].id);
      }
}


// Work over each prime and identify it's neighbours, then look for sequences
for (var i=0; i<primes.length; i++){
      neighbours=calculateNeighbours(primes[i]);

      // Check for sequences in neighbours
      for (var r=0; r<neighbours.length; r++){
	      if (! neighbours[r]){
		    // Don't check anything that returned false
		    continue;
	      }
	      
	      var direction = 'r';
	      
	      if (r>1){
		  direction = 'c';
	      }
	      

	      // Get the cell's directional neighbours
	      cnumbers=getDirectionalNeighbours(neighbours[r],direction);
	      
	      // Test if it's part of a sequence (passing cell references in the order they appear in the table
	      seq = isPartOfSequence(cnumbers[0],neighbours[r],cnumbers[1]);
	      
	      if (seq[0] == true){
		  // We found a Fibonnaci like sequence!
		  // But, the rules (now) say each sequence must be > 3 cells, so we need to check for that
		  if (enforceFourWay(seq[3],direction)){
			colourSequenceMembers(seq[3]);
			selecs.push([neighbours[r],primes[i]]);
		  }
		  
		  
	      }else{
		  // Check the neighbours neighbours - just in case the prime is sat at the end of a sequence
		  nnumbers=getDirectionalNeighbours(cnumbers[0],direction);
		  seq = isPartOfSequence(nnumbers[0],cnumbers[0],nnumbers[1]);

		  if (seq[0] == true){
		      // We found a Fibonnaci like sequence!
		    
		      // Apply the 4 cell rule
		      if (enforceFourWay(seq[3],direction)){		    
			    colourSequenceMembers(seq[3]);
			    selecs.push([neighbours[r],primes[i]]);
		      }
		  }
		  
		  // And the other direction
		  nnumbers=getDirectionalNeighbours(cnumbers[1],direction);
		  seq = isPartOfSequence(nnumbers[0],cnumbers[1],nnumbers[1]);

		  if (seq[0] == true){
		      // We found a Fibonnaci like sequence!
		    
		      // Apply the 4 cell rule
		      if (enforceFourWay(seq[3],direction)){
			  colourSequenceMembers(seq[3]);
			  selecs.push([neighbours[r],primes[i]]);
		      }
		      
		  }
	      }
	      
	      
      
      }
      
}

// Work through and start calculating char codes
for (i=0; i<selecs.length; i++){
      ele = document.getElementById(selecs[i][0]);
      pele = document.getElementById(selecs[i][1]);
      ele.className='selected'; 
      pele.className = 'detectedPrime';
      
      prime=parseInt(pele.innerHTML);
      sno=parseInt(ele.innerHTML);
      computedchar = sno - prime;
      // Discard anything not resulting in a printable asci char
      if (computedchar > 127 || computedchar < 32){
	  continue;
      }

      // Numbers should be read left to right, so we need to get column number ready for sorting later
      ref = decodeReference(selecs[i][0]);
      
      ks.push(ref[1]);
      nums["c"+ref[1]] = computedchar;
}


// Sort the columns into Left -> Right order
ks.sort(sortNumber);

// Work through and print the characters in order
s='';

for (var i=0; i<ks.length; i++){
    s += String.fromCharCode(nums['c'+ks[i]]);
}


alert("Passphrase is: " +s);

#!/usr/bin/env python
#
# Automatically solve puzzle-201604 and recover the password
#
# Pass the script any argument on the commandline to have it automatically decrypt the bounty
#
# (c) 2016 B Tasker
#

import requests, math,sys
from lxml import etree

primes = []
selecs = []
ks = {}
passphrase = []
pagecontent = False
column = 0

def fetchPage():
	''' Get the page contents
	'''
	global pagecontent
	if not pagecontent:
		r = requests.get("https://www.bentasker.co.uk/puzzles/puzzle-201604.html")
		Page = etree.HTML(r.content)
	return Page

def fetchPuzzle():
	''' Extract the puzzle table from the DOM
	'''
	tree = fetchPage()
	return tree.xpath('//table//tr')


def fetchFile():
	''' Get the bounty file from the DOM
	'''
	tree = fetchPage()
	return tree.xpath('//pre[@id="filecontents"]//text()')


def checkNumPrime(n):
	''' Check whether n is a prime number
	'''

	# Numbers less than 4 are all prime
	if n < 4:
		return True

	# Numbers divisible by 2 or 3 aren't prime
	if n%2 == 0 or n%3 == 0:
		return False

	# Create the seeds
	di=2
	i=5

	# Work out the square root of n (no need to check anything higher)
	lim = math.floor(math.sqrt(n))

	while i < lim:
		if n%i == 0:
			return False

		i=i+di
		di=6-di

	# If we got this far, didn't find a whole number. Number is prime
	return True



def getCellValueById(cellid):
	''' The equivalent of doing document.getElementById(cellid).innerHTML in JS
	'''
	global puzzletable
	return puzzletable[0].xpath('//tr//td[@id="'+cellid+'"]//text()')[0];


def decodeReference(cell):
	''' Break a cell ID into a dict containing row and column
	'''
	cell = cell[1:]
	return cell.split('c')


def calculateNeighbours(cell):
	''' Calculate the IDs of neighbouring cells
	'''
	if not cell:
		return False

	reference = decodeReference(cell)
	neighbours = []

	incr = int(reference[0]) +1
	incc = int(reference[1]) +1
	decr = int(reference[0]) - 1
	decc = int(reference[1]) - 1

	
	# Prevent negatives - we don't want to fall off the grid
	if decr >= 0:
		neighbours.append("r"+str(decr)+"c"+reference[1])
	else:
		neighbours.append(False)

	if incr < 20:
		neighbours.append("r"+str(incr)+"c"+reference[1])
	else:
		neighbours.append(False)

	if decc >= 0:
		neighbours.append("r"+reference[0]+"c"+str(decc))
	else:
		neighbours.append(False)

	if incc < 20:
		neighbours.append("r"+reference[0]+"c"+str(incc))
	else:
		neighbours.append(False)

	return neighbours


def getDirectionalNeighbours(cellid,direction):
	''' Get neighbours moving either longitudinally (c) or latidudally (r)
	'''

	# Shouldn't actually happen, but be safe
	if not cellid:
		return [False,False,False,False]

	neighbours = calculateNeighbours(cellid)
	dirneighbours = []
	if direction == "c":
		dirneighbours.append(neighbours[0])
		dirneighbours.append(neighbours[1])
	else:
		dirneighbours.append(neighbours[2])
		dirneighbours.append(neighbours[3])

	return dirneighbours


def isPartOfSequence(c1,c2,c3):
	''' Check whether cells form part of a sequence - Fn = Fn-1 + Fn-2
	'''
	if not c1 or not c3:
		return [False,False,False,[c1,c2,c3]]

	n1 = int(getCellValueById(c1))
	n2 = int(getCellValueById(c2))
	n3 = int(getCellValueById(c3))

	seq = False
	order = False
	cells = [c1,c2,c3]

	# Sequences can be asc or desc, test both

	if n1 + n2 == n3:
		seq = True
		order = 'asc'
	elif n1 - n2 == n3:
		seq = True
		order = 'desc'

	return [seq,True,order,cells]


def enforceFourWay(cells,direction):
	''' Enforce the four cell rule
	'''
	dnb = getDirectionalNeighbours(cells[0],direction)
	dseq = isPartOfSequence(dnb[0],cells[0],dnb[1])
	if not dseq[0]:
		# Check the other end of the sequence we found
		unb = getDirectionalNeighbours(cells[2],direction)
		return isPartOfSequence(unb[0],cells[2],unb[1])[0]

	# dseq found an additional
	return True
	

def asint(s):
	''' Stackoverflow poach - helps sort a dictionary numerically
	'''
	try: return int(s), ''
	except ValueError: return sys.maxint, s


def DecryptFile(pw):
	''' Take the recovered password and decrypt the bounty
	'''
	import tempfile,os
	from pipes import quote
	from subprocess import check_output

	filecontent=fetchFile()[0]
	tmphandle,tmpfile = tempfile.mkstemp()
	f = open(tmpfile,'w')
	f.write(filecontent)
	f.close()
	os.close(tmphandle)
	cmd = "openssl enc -aes-256-cbc -a -d -salt -k "+quote(pw)+" -in "+tmpfile
	output = check_output(cmd,shell=True)
	os.remove(tmpfile)
	return output



if __name__ == '__main__':
	try:
		if sys.argv[1]:
			decrypt=True
	except:
		decrypt=False


	puzzletable = fetchPuzzle()
	# Pick the primes out of the table by iterating over the cells
	while column < 20:
		row = 0
		while row < 20:
			cellref='r'+str(row)+'c'+str(column)
			if checkNumPrime(int(getCellValueById(cellref))):
				primes.append(cellref)
			row = row +1
		column = column + 1



	# Work over each prime and identify it's neighbour
	for prime in primes:
		neighbours = calculateNeighbours(prime)
		# Check neighbours for sequences
		for r,neighbour in enumerate(neighbours):
			if not neighbour:
				continue

			direction = "r"

			if r > 1:
				direction = "c"

			# Get the cells directional neighbours
			cnumbers = getDirectionalNeighbours(neighbour,direction)

			# Check for a sequence in those neighbours
			seq = isPartOfSequence(cnumbers[0],neighbour,cnumbers[1])
			if seq[0]:
				# We found a matching sequence, need to make sure there's >= 4 cells in the sequence
				if enforceFourWay(seq[3],direction):
					selecs.append([neighbour,prime])
			else:
				# Check the neighbour's neighbours - the prime might be sat on the last in a sequence
				nnumbers=getDirectionalNeighbours(cnumbers[0],direction)
				seq = isPartOfSequence(nnumbers[0],cnumbers[0],nnumbers[1])
				if seq[0]:
					# Fourway
					if enforceFourWay(seq[3],direction):
						selecs.append([neighbour,prime])

				# Now check in the other direction
				nnumbers=getDirectionalNeighbours(cnumbers[1],direction)
				seq = isPartOfSequence(nnumbers[0],cnumbers[1],nnumbers[1])
				if seq[0]:
					# Fourway
					if enforceFourWay(seq[3],direction):
						selecs.append([neighbour,prime])


	# Start calculating the char codes
	for select in selecs:
		ele = int(getCellValueById(select[0]))
		pele = int(getCellValueById(select[1]))

		computed = ele - pele
		# Skip non printable ASCII Char codes
		if computed > 127 or computed < 32:
			continue

		# Numbers need to be decoded left to right, so we still care about cell ids
		ref = decodeReference(select[0])
		ks[str(ref[1])] = computed


	# Sort into column order
	for key in sorted(ks,key=asint):
		passphrase.append(chr(ks[key]))


	pw = ''.join(passphrase)
	print "Password: "+pw

	if decrypt:
		print DecryptFile(pw)