{"id":1686,"date":"2014-01-16T20:53:15","date_gmt":"2014-01-16T19:53:15","guid":{"rendered":"https:\/\/ridgesolutions.ie\/?p=1686"},"modified":"2014-03-02T20:31:58","modified_gmt":"2014-03-02T19:31:58","slug":"new-scientist-enigma-1780-and-python","status":"publish","type":"post","link":"https:\/\/www.ridgesolutions.ie\/index.php\/2014\/01\/16\/new-scientist-enigma-1780-and-python\/","title":{"rendered":"New Scientist Enigma 1780 and Python"},"content":{"rendered":"

\"Python
\nSometimes a body has to take a break from all this Software Engineering stuff and instead delve into some recretional programming, so with this in mind I decide to see if I could write a small python program to solve the New Scientist<\/a> Enigma #1780<\/a>. This enigma is kind of like suduku on an icosahedron<\/a> of all things (a 20 faced thing).<\/p>\n

Anyway it was just for fun and I wasn’t looking for the ‘best’ or most ‘elegant’ solution to the problem, just one that kinda worked! So I wrote a little program over Christmas which I got working (more or less).<\/p>\n

I enjoyed the challenge decided to try my hand at future enigmas – only to find out that Enigma #1780 was the last one ever, the New Scientist is giving them up – which is a great pity seeing as I have only started to get interested in them.<\/p>\n

Today I came across this<\/a> site which has python solutions for tonnes of Enigmas including 1780, it was on this site that I learned that 1780 is the last enigma. They point out that there is a large archive of enigmas.<\/p>\n

In an attempt to codify the puzzle, I decided think about the flattened out icosahedron (its net) as a grid of 4 rows of 5 triangles, in this way an individual triangle can be referenced using a pair of numbers (i, j), where i varies between 0 and 4 and specifies the triangle’s ‘column’ while j specifies its row. Next I tried to come up with some rules that would find the coordinates of all of the triangles ‘connected’ to the triangle at (i, j).<\/p>\n

Once all of that is done solving the puzzle given a valid input net is a matter of finding an empty triangle, finding the set of numbers that can go into that triangle, picking one of these numbers and recursively solving the puzzle for the update net, if the recursive solve fails for that number we try the next number and so on….<\/p>\n

Anyway, the solve() function is called like this:<\/p>\n

\r\nsolve(start_net, 0)\r\n<\/pre>\n
\r\n#\r\n# Try to solve New Scientist Enigma 1780 (the last one!)\r\n#\r\n# Run like:\r\n#\r\n# solve(start_net, 0)\r\n#\r\nall_values = {1, 2, 3, 4, 5}\r\n\r\nnet_width = 5\r\nnet_height = 4;\r\n\r\n# get the value at (i, j)\r\ndef value_at(net, a):\r\n    i, j = a\r\n    return net[i + j * net_width]\r\n\r\n# set the value at (i, j)\r\ndef set_value_at(net, a, val):\r\n    i, j = a\r\n    net[i + j * net_width] = val\r\n\r\n\r\n# Create list to hold net values, initialised with zeros\r\nstart_net = [0] * (net_height * net_width)\r\n\r\n# insert the starting values\r\nset_value_at(start_net, (0,0), 2)\r\nset_value_at(start_net, (0,1), 5)\r\nset_value_at(start_net, (0,3), 1)\r\n\r\nset_value_at(start_net, (4,0), 4)\r\n#set_value_at(start_net, (4,2), 3)\r\nset_value_at(start_net, (4,3), 2)\r\n\r\n\r\n# loop i around if i > net_width (modulo)    \r\ndef mi(i):\r\n    return i % net_width\r\n\r\n# The connection rules for each row\r\ni_0 = [lambda i: (mi(i+1), 0), lambda i: (mi(i+2), 0), lambda i: (mi(i+3), 0), lambda i: (mi(i+4), 0), lambda i: (mi(i-1), 1),\r\n       lambda i: (mi(i-1), 2), lambda i: (mi(i), 1), lambda i: (mi(i+1), 2), lambda i: (mi(i+1), 1)]\r\n\r\ni_3 = [lambda i: (mi(i+1), 3), lambda i: (mi(i+2), 3), lambda i: (mi(i+3), 3), lambda i: (mi(i+4), 3), lambda i: (mi(i-1), 2),\r\n       lambda i: (mi(i), 1), lambda i: (mi(i), 2), lambda i: (mi(i+1), 1), lambda i: (mi(i+1), 2)]\r\n\r\ni_1 = [lambda i: (mi(i-1), 0), lambda i: (mi(i-1), 1), lambda i: (mi(i-1), 2), lambda i: (mi(i-1), 3), lambda i: (mi(i), 0),\r\n       lambda i: (mi(i), 2), lambda i: (mi(i), 3), lambda i: (mi(i+1), 0), lambda i: (mi(i+1), 1)]\r\n\r\ni_2 = [lambda i: (mi(i), 0), lambda i: (mi(i), 1), lambda i: (mi(i), 3), lambda i: (mi(i-1), 2), lambda i: (mi(i-1), 3),\r\n       lambda i: (mi(i+1), 0), lambda i: (mi(i+1), 1), lambda i: (mi(i+1), 2), lambda i: (mi(i+1), 3)]\r\n\r\ncons = [i_0, i_1, i_2, i_3]\r\n\r\n# is a connected to b?\r\ndef connected(a,b):\r\n    (i, j) = a\r\n    \r\n    if a == b:\r\n        return True;\r\n\r\n    return b in [d(i) for d in cons[j]]\r\n\r\n# gets a list of all triangle coordinates\r\ndef all_triangles():\r\n    return [(i % net_width, i \/\/ net_width) for i in range(0,net_height*net_width) ]\r\n\r\n# gets a list of all triangles connectd to a    \r\ndef connected_triangles(a):\r\n    return [b for b in all_triangles() if connected(a,b)]\r\n\r\ndef find_loc_of_first_empty_triangle(net):\r\n    try:\r\n        index = net.index(0)\r\n        return (index % net_width, index \/\/ net_width)\r\n    except:\r\n        return None \r\n\r\n# returns a list of all empty triangles\r\ndef all_empty_triangles(net):\r\n    return [a for a in all_triangles() if value_at(net, a) == 0]\r\n\r\n# returns the possible values (1..5) that can go into\r\n# the triangle a\r\ndef possible_values(net, a):\r\n    ct = connected_triangles(a)\r\n    used_values = {value_at(net, t) for t in ct}\r\n    return all_values - used_values - {value_at(net, a)}\r\n    \r\n\r\n# solve given a valid input net    \r\ndef solve(net, depth):\r\n    print ('solve, depth: ' + str(depth))\r\n    a = find_loc_of_first_empty_triangle(net)\r\n    \r\n    # if there are no free locations then the\r\n    # net if full and we have finished\r\n    if not a:\r\n        print ('net is full ' + str(net))\r\n        return net\r\n    \r\n    # get list of possible values for this triangle\r\n    possible = possible_values(net, a)\r\n    \r\n    # If we can't make a move then we need\r\n    # to backtrack\r\n    if not possible:\r\n        print ('No more possible moves for ' + str(a))\r\n        return []\r\n    \r\n    for v in possible:\r\n        \r\n        # create a copy of our current net\r\n        new_net = list(net)\r\n        \r\n        set_value_at(new_net, a, v)\r\n        result_net = solve(new_net, depth+1) \r\n\r\n        if result_net:\r\n            return result_net\r\n\r\n    return []\r\n\r\nif __name__ == \"__main__\":\r\n    res = solve(start_net, 0)\r\n#    \r\n<\/pre>\n
Update, 07\/02\/2014<\/strong>
\nThe answer to this Enigma as announced here<\/a> is: 324125, thankfully the same as that announced by the Python program!  Unfortunately I didn’t win the competition, but I had loads of fun trying to write some software to solve it!  I might try a Haskell version next if I find the time…<\/p>\n","protected":false},"excerpt":{"rendered":"
Sometimes a body has to take a break from all this Software Engineering stuff and instead delve into some recretional programming, so with this in mind I decide to see if I could write a small python program to solve the New Scientist Enigma #1780. This enigma is kind of like suduku on an icosahedron […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[301],"tags":[304,303,305],"class_list":["post-1686","post","type-post","status-publish","format-standard","hentry","category-by-kevin-godden","tag-enigma","tag-new-scientist","tag-pyhon"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t