Hi All,
No brass band music - not a Monty Python Sketch(for those in the know). Just a small challenge, as requested by a few forum members. Link below describes the challenge in detail. This is meant to be a beneficial challenge to make you use your grey matter and broaden your programming experience. Fire up any issues/problems you have. Hoping to see a variety of solutions. I’ll post mine later. Hope you enjoy.
Edit: first off need to think on how to represent the mats within the project.
@Bri_G I compressed it down so much that looking at it I don’t understand what I was doing. The worst part is the if statement in the function compare(). All the other code is pretty much straight forward. In that if statement, I’m increment my way thru all the disk rotations 1,1,1,1 thru 16,16,16,16 and each time comparing the animal pairs at the 4 connecting positions. If they’re all equal I print the results.
@dave1707, @Loopspace - having worked through all this it made me wonder what the extra complication of coloured segments in the mats would introduce to designing puzzles like this. Both @dave1707 and myself (in my original program in 1980) assumed it was crucial to the resolution and catered for it.
@Bri_G I originally had the background color as part of the puzzle. When @LoopSpace asked about it, I removed it from my compare and it didn’t affect the outcome at all. I think if there were more duplicate animal pairs, then maybe the background color could play a part.
I completed my code for solving the puzzle using a direct method. It prints the final answer a little different than my original program, but it’s still the correct answer. I don’t think I’m going to compress this down like I did the first one and I’m trying to display a paper trail showing what it’s doing so I can make the disks and follow along to see how it found the answer.
I’m going to have a go at explaining my approach. It reduces the number of configurations to check from approximately 300,000 to about 200. The time saving is considerable.
My code is available as a gist.
The key idea is that once we have established that two discs can’t be placed next to each other a particular way round, then we can exclude all configurations in which those two discs appear that particular way round. This makes the search space much, much smaller.
One way to implement this is via back-tracking. That’s essentially what I do, but I do a bit of analysis first to convert the data into a graph and then use that to set up the algorithm.
Firstly, my way to encode the discs is as follows: I assign each side a letter with the convention that a lowercase letter matches its uppercase version. Thus a matches A, b matches B, and so forth. I got 32 sides in total, giving 16 pairs. I then converted these to numbers. As lua is 1-based, I used 1 to 32. It would have been slightly easier to use 0 to 31 as then toggling the case is equivalent to XORing with 16.
I then converted the arrangements on the discs into a graph. By graph here, I mean a collection of nodes and edges. Each edge connects two nodes. The nodes are thought of as just points, but in this case they have labels. We label the nodes by the possible matched sides. So a label might be aA meaning that we have a disc with side a next to a disc with side A (but without specifying which discs these are). We also use the convention that aA means that the disc with a comes first when working anti-clockwise. This allows us to distinguish between aA and Aa. We therefore have 32 nodes.
In my program, I actually use numbers to label the nodes using the ordering Aa, Bb, Cc, Dd, …, aA, bB … and so on.
The edges in the graph correspond to the discs themselves. The edges are actually directed, meaning that they point from one node to another node. A disc defines an edge from, say, Aa to Gg if that disc can be placed so that it forms the a part of the Aa matched side and the G part of the Gg matched side. For this to happen, the disc must have an a side, then something else, and then a G side. So we can figure out the edges by looking at the lists of sides of the discs. There are 8 x 2 x 4 = 64 edges in total.
We also label the edges so that we remember which disc they came from, which side of that disc, and which angle the disc is turned through. This helps with reconstructing the configuration at the end.
We now do a search through the graph. We are looking for a cycle, meaning a path that starts and ends at the same edge. The cycle must have length 4 (for the 4 discs), and the four edges must be labelled by distinct discs.
The search proceeds as follows: at each step, we have a current node. We try adding an edge from that node. The edges that can be added are those which don’t come from a disc that has already been added. In order to get started, we add an extra node and link it to every node that has an edge labelled by the first disc (since the first disc has to be used, we may as well use it first).
If we’re interested in just finding the solution, we can simply run the search on this graph. But in order to make it possible to view the search, I set it up in a coroutine which would yield after every step.
The search algorithm works recursively as follows:
n.n, for each edge that corresponds to a disc which is not yet represented in the path, append that edge to the path. Then call this algorithm on the new, extended path. Once that version of the algorithm finishes, remove the new edge and append the next one.n have been considered.So at each stage, we try to extend the current path.
If we can, we continue until either we can’t or we have a solution. If we can’t, we remove the last component (“back track”) and try again with a new edge at that point.
In actual fact, this doesn’t quite find solutions. It finds paths which use all four discs so that the connections from first to second to third to fourth are valid. It doesn’t check the final connection from fourth back to first, but any potential solution can be quickly checked for this.
It also finds the solution twice. This is because the starting condition is all sides that appear on the first disc. Some of them happen to appear on other discs, so the first edge attached to the path might not be the first disc. It therefore finds the correct solution twice, but the second is a rotation of the first. Again, this can be easily checked for.
The times that I get with this approach are of the order of: 0.0004s to initialise the problem, then the solution is found at 0.0005s, and the whole thing is completed at 0.0009s. These numbers obviously fluctuate on runs, but those are the largest numbers I have recorded.
I’ll post my actual code soon. I want to go through it and add comments. I’m not sure how clear the above is, particularly to those unfamiliar with graphs and graph traversal algorithms. I’m happy to consider comments/questions that will help clarify the exposition.
@Loopspace - that’s a lot to take in initially. I think I need to see your code alongside your description to fully appreciate the approach. On the 300,000 to 200 front - is that with this particular data set or will it be similar with other data sets?
Think I’ll outline my approach in text to help anyone following this thread.
@LoopSpace I’m having a hard time following what you’re writing. I’ll have to read it several times, then maybe it’ll start to make sense to me. Is this like a binary tree search, if not I wonder if one would work. I would try it but l never could figure out how to do one.
@dave1707 - LOL, I’ve been busy putting lines back into your code so that I can read it better. Have you looked at the authors code in the website C&VG published. He used numbers but split each face up into 8 characters representing half of a face. I have lost the original discs and so had to derive the original layouts from my own code - not ideal and I have struggled to understand why he used this format.
Now I’m trying to strip back my own code to micro minimise it with @Loopspace’s approach to only test downstream if you hit valid entries on the path. Can’t believe the speeds we are getting relative to the 39 year old veteran gear.
@Bri_G It took 172 seconds to run the 1000 combinations. I used this code, but I included a 1000 count loop around the couple of statements in setup. In that loop, I also included code that would fill the table with random pairs each time.
When I started coding this, I just had the animal pairs in the table. Putting the mirror pairs in the table eliminated a lot of code trying to swap the animals. The code was also a lot bigger than this and I just kept changing the code until I couldn’t find anything else to change. It’s not very readable, so it’s hard to see exactly what’s happening.
@timber I think we’re doing the same thing. You put your disks in 1,2,4,3 order going clockwise. Then your disks are placed
12
34.
My disks are also
12
34
My code is written to look at the disks in 1,2,3,4 order.
I’ll post my brute force code here as soon as @Bri_G says it’s OK.
@dave1707 - ah ok that makes sense. Now I know I have the right answer will try and streamline the code. Interested to see how others have approached it - especially the graph approach. Thanks for explanation
All - I put a link in my website to the Internet Archive which houses many computer based publications. This includes C&VG and here is a link to the issue with the puzzle in.
Ps. Tap go at the prompt.
Two other issues released a picture of the solution and the Basic language code which I have quoted. Anyone needing a basic outline for games may consider looking through a few of these - may fire up a few ideas. Published fro 1980 until October 2004.
Here’s my brute force code that search’s only the disk orientation for
12
34.
The number of lines of code here varies depending on the device and orientation, but there are 32 numbered lines in the editor.
This prints out
15 xl 5 ft 9 xf 10 pt
The numbers 15, 5, 9, 10 is the front or back of the disk. 1 to 8 is front, 9 to 16 is back. So it’s back, front, back, back.
The xl, ft, xf, pt is the animal pairs at the 6 o’clock position of the disks.
(xl for fox,lion) (ft for frog,tiger) (xf for fox,frog) (pt for panda,tiger).
See the link above SolutionBMsm.png that@Bri-G posted of the solution
I’m still working on a direct solution to eliminate dead end searches.
I’m not posting this with the ~~~ (3 tildes) at the start and end. If I do, it doesn’t display the full table. You can format it if you want, but it runs OK as posted.
function setup()
tab={{{“lt”,“tl”},{“pf”,“fp”},{“up”,“pu”},{“lr”,“rl”},{“px”,“xp”},{“xl”,“lx”},{“xt”,“tx”},{“pu”,“up”},{“pr”,“rp”},{“rx”,“xr”},{“pf”,“fp”},{“ft”,“tf”},{“tp”,“pt”},{“rx”,“xr”},{“xl”,“lx”},{“rl”,“lr”},},{{“lf”,“fl”},{“fp”,“pf”},{“rp”,“pr”},{“pt”,“tp”},{“ft”,“tf”},{“xp”,“pp px”},{“rl”,“lr”},{“fx”,“xf”},{“tr”,“rt”},{“px”,“xp”},{“fx”,“xf”},{“rf”,“fr”},{“xr”,“rx”},{“ft”,“tf”},{“tl”,“lt”},{“tx”,“xt”},},{{“lr”,“rl”},{“pr”,“rp”},{“lf”,“fl”},{“rt”,“tr”},{“lt”,“tl”},{“pu”,“up”},{“fr”,“rf”},{“xu”,“ux”},{“xf”,“fx”},{“rp”,“pr”},{“xu”,“ux”},{“rf”,“fr”},{“lx”,“xl”},{“tr”,“rt”},{“tp”,“pt”},{“xt”,“tx”},},{{“lx”,“xl”},{“tf”,“ft”},{“tx”,“xt”},{“xf”,“fx”},{“tl”,“lt”},{“fl”,“lf”},{“ux”,“xu”},{“fr”,“rf”},{“xr”,“rx”},{“pt”,“tp”},{“rt”,“tr”},{“up”,“pu”},{“xp”,“px”},{“tf”,“ft”},{“fl”,“lf”},{“ux”,“xu”},},}
disk={1,1,1,1} – set starting values for each disk
while not done do – loop thru all disk positions until done
compare()
end
end
function compare() – compare 4 image pairs at the connecting points
if tab[1][rotate(1,0)][1]==tab[3][rotate(3,4)][2] and tab[1][rotate(1,2)][1]==tab[2][rotate(2,6)][2] and tab[2][rotate(2,0)][1]==tab[4][rotate(4,4)][2] and tab[3][rotate(3,2)][1]==tab[4][rotate(4,6)][2] then
print(disk[1],tab[1][disk[1]][1],disk[2],tab[2][disk[2]][1],disk[3],tab[3][disk[3]][1],disk[4],tab[4][disk[4]][1])
end
for z=4,1,-1 do – increment the values in the disk table
disk[z]=disk[z]+1
if disk[z]>16 then
if z==1 then
done=true – if disk[1] >16, we’re done.
end
disk[z]=1
else
break
end
end
end
function rotate(p,a) – move the value in disk[p] thru the table.
temp=disk[p]+a
if disk[p]>8 and temp>16 or disk[p]<9 and temp>8 then
temp=temp-8
end
return temp
end
@dave1707 - neat, ran the code and it looked to have printed the result before the tool window was fully visible. Interesting way to store the image orientations in pairs. I tried a few options with my string system. Tried a reverse string but would have to work backwards with that, then I tried a duplicate string constructed by selecting each pair reversing and building up the string - this had the advantage that the addressing of the pairs is identical but with different strings. These options obviously add time on the procedure but I would argue that they are not really part of the cycle time and could be run prior to the timing loop. Then again I thought I could just run a separate project to build and write the reverse data to a separate tab for inclusion in a separate evaluation.
That reminds me I was intrigued to read that you had built up 1000 random 4 disc sets and then tested them. Was this in a single project and how long did that run?
@dave1707 I also get only one solution but my order of beer mats is 1,2,4,3 going clockwise. I don’t find a solution 1,2,3,4 orientation as per your post. I have tried it with the physical beer mats and can send a photo. Code needs tidying up a lot but sounds similar to your clock face approach (but more lines of code - won’t get close to 34 lines without a major rethink). Cheers @Bri_G for testing my grey matter
@timber - you’re welcome. I found this an intriguing puzzle and worth resurrecting. I’ve updated the website to show the solution and am appending an image here to display it so you can check it out yourself. The thread is about how you derive it not what the solution is.
Okay, I have a solution.
My method was to build a graph of the pieces. The nodes in the graph are the different edge types of the pieces. I connect one edge type to another if there is an octagon which can be placed so that the two edges are used in the puzzle.
Solving the puzzle is then finding a 4-cycle through this graph, which can be done by a traversal of the graph.
This graph has only 32 nodes and 64 edges, so the traversal is quite fast. But I think we should count something other than seconds in evaluating code. I’d like to propose that if we imagined following what the code was doing by hand, how many configurations of the pieces would get laid out when following the code?
@dave1707 - I remember the original article written by the author of the puzzle, he said that he had found a novel way to resolve the puzzle but I never saw a follow up. I tried to resolve it by working out the populations of the pairs on each face (and their mirror images) looking for an obvious link but it didn’t work. Most pairs were equal and all balanced - there were a couple with more pairs and a couple with less but only one was involved with the solution. I`m still looking for another approach.
@Loopspace - interesting seeing your approach, mathematically driven. Never conceived that a graph could help. By configurations do you mean details of each configuration or just the number. I have a counter in my solution which could be modified if necessary to produce more stats?
Edit: @Loopspace - could you email details of the solution configuration, just to check it’s identical with that from mine and @dave1707 ? Disc position angle and faceID would do. A different approach may throw up a different result but I doubt it.
@LoopSpace @Bri_G I do something similar, but instead of a graph, I use the face of a clock analogy. For the upper left disk, the compare positions are a 3 and 6 o’clock. For the upper right, it 9 and 6 o’clock. For the lower left, it’s 12 and 3 o’clock. And the lower right it’s 9 and 12 o’clock. I compare what’s at those positions as I rotate the disks. So I compare, rotate, compare, rotate, etc as the disks rotate thru all of their cycles. It takes 65,536 moves to go thru all the combinations for that disk layout. Since there’s 6 different disk layouts, then it’s 393,216 total moves.