Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

And now for something completely different....

edited November 18 in Code Sharing Posts: 1,400

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.

The Beermat Challenge

Edit: first off need to think on how to represent the mats within the project.

Tagged:
«1

Comments

  • dave1707dave1707 Mod
    edited November 11 Posts: 7,923

    Just so you know, it can be done. My program ran in .17 seconds to give a text answer of how the disks should be flipped and rotated. Just for some help, I didn’t mess around with any graphics until I sent the solution to @Bri_G showing the positions/rotation of the 4 disks for verification. I thought it was a very interesting challenge. Thanks @Bri_G. I’ll post my code at a later date just so I don’t spoil it for others.

  • Posts: 1,400
    @dave1707 - how have you measured the time at less than a second. Always thought Lua's minimum time was a second or zero?
  • dave1707dave1707 Mod
    Posts: 7,923

    @Bri_G I use gettime from sockets. Keep changing the number of zeroes in the for loop and watch the time change by a factor of ten.

    function setup()
        s=require("socket")
        st=s:gettime()
        for z=1,10000 do
            a=math.sqrt(z)
        end
        en=s:gettime()
        print(en-st)
    end
    
  • edited November 11 Posts: 1,400

    @dave1707 - thanks for the timer util, never have thought of using socket. Does that vary with your internet server etc? My solution did it in 0.88 secs - stripped out the sprites I use and it dropped to 0.87 sec!!!! I also have a few variables and build print statements that could be eliminated to tidy up but I can’t see me getting much lower. How many lines of code are you using?

  • dave1707dave1707 Mod
    edited November 12 Posts: 7,923

    @Bri_G The socket code is pulled into Codea with the require, so gettime is a function call just like anything else. Not sure if it slows down if the FPS gets really low. I’ll have to try that.

    My code is 75 lines.

    PS. I was able to optimize my code and group like code. That brought the size of my code down to 50 lines.

  • edited November 12 Posts: 1,400
    All,
    Anyone out there trying to program a solution? Like to know - give me some idea on when to publish solution.
  • dave1707dave1707 Mod
    Posts: 7,923

    This may or may not help, but here’s an example of spinning 4 disks looking for a match at the four green compare positions. Each time this is run, the 4 disks will have different sprite positions. The disks are not spinning when the program starts, tap the screen and disk 4 will spin at full speed. You can open the print window and move the slider to slow it down. The disks will stop when the sprite pairs match in the green rectangles. Tap the screen to continue again. Sometimes there won’t be any match’s, sometimes 1, sometimes a few. The number in the center shows the rotation number for disks 1 thru 4. The numbers will go from 1111 to 8888. It will stop at 8888. To solve @Bri_G challenge, no graphics need to be used. My program to solve his challenge uses no graphics and just prints out the 4 digit rotation number. This program only uses one sided disks and one image to compare, his uses 2 sided disks and uses 2 pictures to compare.

    displayMode(FULLSCREEN)
    
    function setup()
        parameter.integer("delay",0,60,0)
        pic={"Planet Cute:Character Princess Girl","Planet Cute:Character Boy","Planet Cute:Character Cat Girl","Planet Cute:Character Horn Girl","Planet Cute:Character Pink Girl","Planet Cute:Star","Planet Cute:Heart","Planet Cute:Key" }
        fill(255)
        disk={}
        r={}
        for z=1,4 do
            u={1,2,3,4,5,6,7,8}
            disk[z]={}
            r[z]={}
            for y=1,8 do
                h=math.random(#u)
                disk[z][y]=u[h] 
                table.remove(u,h)
                r[z][y]=disk[z][y] 
            end
        end
        p={1,1,1,1}
        cnt=0
        str=""
        found=true
    end
    
    function draw()
        background(224, 198, 134, 255)
        fill(255)
        ellipse(WIDTH/2-200,HEIGHT-220,370)
        ellipse(WIDTH/2+200,HEIGHT-220,370)
        ellipse(WIDTH/2-200,HEIGHT-600,370)
        ellipse(WIDTH/2+200,HEIGHT-600,370)
        fill(0)
        ellipse(WIDTH/2-200,HEIGHT-220,200)
        ellipse(WIDTH/2+200,HEIGHT-220,200)
        ellipse(WIDTH/2-200,HEIGHT-600,200)
        ellipse(WIDTH/2+200,HEIGHT-600,200)
        fill(0, 255, 93, 255)
        rect(WIDTH/2-100,HEIGHT-260,200,80)
        rect(WIDTH/2-100,HEIGHT-640,200,80)
        rect(WIDTH/2-240,HEIGHT-500,80,180)
        rect(WIDTH/2+160,HEIGHT-500,80,180)
        show(1,WIDTH/2-200,HEIGHT-70)
        show(2,WIDTH/2+200,HEIGHT-70)
        show(3,WIDTH/2-200,HEIGHT-450)
        show(4,WIDTH/2+200,HEIGHT-450)
        fill(255,0,0)
        text("Disk 1",WIDTH/2-200,HEIGHT-220)
        text("Disk 2",WIDTH/2+200,HEIGHT-220)
        text("Disk 3",WIDTH/2-200,HEIGHT-600)
        text("Disk 4",WIDTH/2+200,HEIGHT-600)
        cnt=cnt+1
        if cnt>delay then
            add()
            cnt=0
        end
        if done then
            str="search complete, press restart icon"
        else
            str=string.format("%2d %2d %2d %2d",p[1],p[2],p[3],p[4])
        end
        text(str,WIDTH/2,HEIGHT-400)
        text("tap screen to pause or continue",WIDTH/2,50)
    end
    
    function touched(t)
        if t.state==BEGAN then
            found=not found
        end
    end
    
    function show(d,x,y)
        sprite(pic[r[d][5]],x,y,80)
        sprite(pic[r[d][6]],x-100,y-50,80)
        sprite(pic[r[d][4]],x+100,y-50,80)
        sprite(pic[r[d][7]],x-140,y-140,80)
        sprite(pic[r[d][3]],x+140,y-140,80)
        sprite(pic[r[d][8]],x-100,y-230,80)
        sprite(pic[r[d][2]],x+100,y-230,80)
        sprite(pic[r[d][1]],x,y-280,80)
    end
    
    function add()
        if found or done then
            return
        end
        for a=4,1,-1 do
            p[a]=p[a]+1
            if p[a]>8 then
                if a==1 then
                    done=true
                end
                p[a]=1
            else
                break
            end
        end
        for x=1,4 do
            s=p[x]
            for y=1,8 do
                r[x][y]=disk[x][s]
                s=s+1
                if s>8 then
                    s=1
                end
            end
        end
        if r[1][1]==r[3][5] and r[1][3]==r[2][7] and r[2][1]==r[4][5] and r[4][7]==r[3][3] then
            found=true
        end
    end
    
  • Posts: 1,400

    @dave1707 - very neat, great demo. Covers most of the work needed to resolve the puzzle. Interesting to see how you set this up - you get to read how other minds think.

    A first - never seen break used before in anger.

    Thanks for that.

  • dave1707dave1707 Mod
    Posts: 7,923

    @Bri_G There hasn’t been too much activity on this, so I thought I’d give a demo showing what’s going on. While watching the demo, it gave me an idea on maybe another way to solve it.

  • edited November 13 Posts: 1,400
    Hi All,
    Thought I'd post an image from the website header that may help in solving the puzzle. Put two together it may help.
  • Posts: 1,400
    @dave1707 - I spent quite a long time looking into alternative ways of solving the puzzle but usually ran into a brick wall.
  • dave1707dave1707 Mod
    edited November 13 Posts: 7,923

    @Bri_G I don’t think assigning a single number to each pair would help. When you compare the two pictures to the two on another disk, you need the mirror image of the original picture. Using a single number would work if you didn’t care about the orientation of the two images. How you create a table will make things either easier or harder. It’s all in how the table is created.

    I changed what I have in my table and was able to reduce the size of my code to 39 lines. That was optimizing the code and grouping like code. That’s 39 line numbers. If I count the actual lines of code, there are 49. The table, even though it uses one line number, actually takes 12 lines on the screen.

    I’m still trying to find a better way of doing this.

  • Posts: 1,400
    @dave1707 - I made the numbered disc to show that there were 8 faces but, putting two together and rotating to give identical faces opposite each other are mirror images adding a new feature to the testing for matches.
  • dave1707dave1707 Mod
    Posts: 7,923

    @Bri_G I rearranged what’s in my table and I reduced the code from 39 numbered lines to 34. What’s in the table and how it’s arranged is important to the amount of code used to process what’s in it. I find this puzzle a good challenge in how to modify tables to reduce the code needed to solve a problem.

  • edited November 14 Posts: 1,400

    All,
    I have been asked to give a little more description of the actual puzzle - so I have populated the two arrangement skeletons on the website with images of the discs. Both are equivalent and either orientation works and need only minor changes to the code if you switch orientation. Pick which orientation you prefer and place your discs in the selected orientation and compare the 8 touching sides (4 pairs) to see if they match. Then by switching, rotating discs or flipping the sides find one or more configurations that have all 4 pairs matching. Note - by Matching we are talking mirrored images. If you need further explanation don't hesitate to post.

    p.s. You can't get too much of a hint from the attached pictures I have used all front images on one and all back images on the other.

    p.p.s Printing out the discs and folding/glueing them makes the puzzle much clearer.

  • Posts: 457

    When coding jigsaws before, I've used a scheme of assigning a letter to each type of edge with the convention that a capital letter matches the corresponding lowercase letter.

    Using this convention, I get:

    • a robot-fox
    • b panda-frog
    • c frog-tiger
    • d tiger-panda
    • e fox-lion
    • f robot-lion
    • g panda-robot
    • h pumpkin-panda
    • i panda-fox
    • j fox-tiger
    • k lion-tiger
    • l tiger-robot
    • m frog-fox
    • n robot-frog
    • o lion-frog
    • p pumpkin-fox

    With these assignments, I think that the four discs are:

    abcdaefg hFiejHkb
    mnAcKJli GDcIfmoB
    pnEldjMG oLkHNPFg
    LhICOpAD JMKOpNLC
    
  • dave1707dave1707 Mod
    Posts: 7,923

    @LoopSpace Don’t forget about the background color. Some have a white background, others aren’t.

  • Posts: 457

    @dave1707 Oh, I didn't realise that was significant. Bleugh.

  • edited November 13 Posts: 1,400

    @Loopspace - I adopted a similar pattern but used a single letter to represent an image, found out I had a couple of clashes and then had to bend my ‘rules’ a bit to comply so I ended up with:

    P - Panda
    T - Tiger
    L - Lion
    F - frog
    B - for roBot
    R - for fox (Reynard)
    H - for pumpkin (Halloween)
    

    Then represented panda-tiger as PT

    Oh by the way I was right and wrong for my calculation - had my binary series hat on should have been 16x48x32x16 ie the number permutations at each position. But doubled 32 to 64 instead of adding 16. Thanks again for the pointer.

  • dave1707dave1707 Mod
    edited November 13 Posts: 7,923

    @Bri_G I did something similar.
    p=panda, t=tiger, l=lion, f=frog, r=robot, x=fox, u=pumpkin. I then use p=purple and w=white for the background colors. So I had pp=purple panda or wl=white lion.

  • Posts: 457

    @Bri_G Can you confirm that the background colours are significant?

  • Posts: 1,400

    @Loopspace - when I first used Basic to resolve this I included colours in my coding. However, when I read the code from the creator of the puzzle I couldn’t see any programming involving the colour. So my latest code in Codea doesn’t use it. My latest code found the solution - so I would say no, you don’t need it. I don’t know if it was a red herring or if the design of the mats didn’t incorporate it in key areas.

  • dave1707dave1707 Mod
    Posts: 7,923

    I’ll have to try my code without the background colors and see what happens.

  • dave1707dave1707 Mod
    Posts: 7,923

    I removed the background color and I got the same results as before. The only solution was with the 1,2,3,4 orientation. I think if you’re trying to do it manually, the background color might eliminate trying some solutions.

  • dave1707dave1707 Mod
    Posts: 7,923

    @Bri_G I wrote some code that displays the disks next to each other. If I tap on a disk, it rotates clockwise one set of pictures. I found that I can manually solve the puzzle in about 5 minutes. I guess it helps to know in what order the disks should be. Even if I didn’t, then it would take about 30 minutes to go thru all 6 combinations of the 4 disks. So basically the puzzle can be solved manually in less than 30 minutes not knowing the order of the 4 disks.

  • Posts: 1,400
    @dave1707- I still have unfinished versions using the graphics. That's how I started off the I realised I had better finish the basic solution so I could append the front end. I had a few versions I was going to publish on the forum - but need to finish couple before that.

    I think the naked eye can help speed up the solution as you take more in than you think. Also, in this case I think the solution was set up for an quick find as the machine speed when it was designed was relatively very slow.

    But the challenge is in the coding. Your configuration is faster than mine - as I said before my layout runs clockwise.
  • dave1707dave1707 Mod
    Posts: 7,923

    @Bri_G I modified my manual code to keep track of the number of moves before I found the solution. The count was 307 moves.

    My original code to find the solution doesn’t use graphics at all. Making one move per draw cycle is too fast to see what’s happening and then to go thru all the combinations would take an awfully long time. That’s why I skipped the graphics and just printed the final answer of how the disks needed to be rotated.

    I have to admit one thing, this has kept me busy trying different things.

  • Posts: 457

    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?

  • edited November 15 Posts: 1,400

    @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.

  • dave1707dave1707 Mod
    Posts: 7,923

    @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.

  • Posts: 11

    @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

  • edited November 17 Posts: 1,400

    @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.

    Beermat Puzzle Update

  • dave1707dave1707 Mod
    edited November 17 Posts: 7,923

    @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.

  • edited November 17 Posts: 1,400

    @dave1707 - just posted the link to my updated website with solution on it so - post away.

  • Posts: 11

    @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

  • edited November 17 Posts: 1,400

    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.

    C&VG archive

    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.

  • dave1707dave1707 Mod
    edited November 17 Posts: 7,923

    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

  • Posts: 1,400

    @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?

  • dave1707dave1707 Mod
    Posts: 7,923

    @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.

  • edited November 17 Posts: 1,400

    @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.

  • dave1707dave1707 Mod
    Posts: 7,923

    @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.

  • Posts: 1,400

    @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.

  • dave1707dave1707 Mod
    Posts: 7,923

    @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.

  • edited November 20 Posts: 457

    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:

    1. Start with a current path through the graph which ends at node n.
    2. Iterate through the edges attached at 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.
    3. Terminate when all the edges attached at 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.

  • edited November 18 Posts: 1,400
    @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.
  • dave1707dave1707 Mod
    Posts: 7,923

    @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.

  • dave1707dave1707 Mod
    Posts: 7,923

    Here’s my code that searches for solutions, ignoring dead ends. I didn’t compress it or add a lot of comments. It does the whole search in about .000082s (8.2015991210938e-05). There are 45 valid matches. In a copy of this code, I added print statements so I could see what was happening. Using cut outs of the disks, I followed what was going on at each of the searches and everything looked OK. I going to try something else manually to verify what’s happening here. I’ll post that when I finish, but I thought I’d post this anyways.

    function setup()
        s=require("socket")
        st=s:gettime()        
        s1={{"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"},}    
        s2={{"lf","fl"},{"fp","pf"},{"rp","pr"},{"pt","tp"},{"ft","tf"},{"xp","px"},
            {"rl","lr"},{"fx","xf"},{"tr","rt"},{"px","xp"},{"fx","xf"},{"rf","fr"},
            {"xr","rx"},{"ft","tf"},{"tl","lt"},{"tx","xt"},}    
        s3={{"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"},}
        s4={{"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"},} 
        searchCount=0
        for a=1,16 do   -- try each animal pair on disk 1
            d1(a)
        end
        print("Total time "..s:gettime()-st) 
        print("Search count ",searchCount)
        print("***  Slide window top up ***")
    end
    
    function d1(pos)
        f11=pos         -- disk 1 position in table
        c11=s1[f11][1]  -- get image pair from table
        m11=s1[f11][2]  -- get mirror of c11 from table
        f13=f11+2       -- disk 1 position 3 (3 oclock)
        if f11<9 then   -- keep value in range 1-8 or 9-16 based on pos value
            if f13>8 then
                f13=f13-8
            end
        elseif f13>16 then
            f13=f13-8
        end    
        c13=s1[f13][1]  -- image pair
        m13=s1[f13][2]  -- mirror of c13
        s27=1   -- initial search position for disk 2 position 7
        f27=0   -- initial find position for disk 2 position 7
        while f27~=nil do
            m1327(m13)  -- disk 1 position 3, disk 2 position 7
            if f27~=nil then
                s35=1   -- initial search position for disk 3 position 5
                f35=0   -- initial find position for disk 3 position 5
                while f35~=nil do
                    m1135(m11)  -- disk 1 position 1, disk 3 position 5
                    if f35~=nil then
                        s47=1
                        f47=0
                        while f47~=nil do
                            m3347(m33)  -- disk 3 position 3, disk 4 position 7
                            if f47~=nil then
                                m2145() -- disk 2 position 1, disk 4 position 5 
                                if c11==m35 and c13==m27 and c33==m47 and c21==m45 then
                                    print("=====  Match found  =====")
                                    print("(1-8)=Front  (9-16)=Back")
                                    print("D1="..f11.."  D2="..f27.."  D3="..f35.."  D4="..f47)
                                    print("Animal pairs at 6 o'clock position")
                                    print("disk 1 ",s1[pos][1])
                                    print("disk 2 ",s2[f27+2][1])
                                    print("disk 3 ",s3[f35-4][1])
                                    print("disk 4 ",s4[f47-6][1])
                                end
                            end
                        end
                    end
                end
            end
        end
    end
    
    function srch(tab,ch,st)    -- search table tab for animal pair ch, start at st. 
        searchCount=searchCount+1
        for z=st,16 do
            if tab[z][1]==ch then
                return z
            end
        end
        return nil    
    end
    
    function m1327(a)
        if s27>16 then
            f27=nil
        else
            f27=srch(s2,a,s27)
            if f27~=nil then
                s27=f27+1
                c27=s2[f27][1]  -- image pair
                m27=s2[f27][2]  -- mirror of c27
                f21=f27-6
                if f27>8 then
                    if f21<9 then
                        f21=f21+8
                    end
                elseif f21<1 then
                    f21=f21+8
                end
                c21=s2[f21][1]  -- image pair
                m21=s2[f21][2]  -- mirror of c21
            end
        end
    end
    
    function m1135(a)
        if s35>16 then
            f35=nil
        else
            f35=srch(s3,a,s35)
            if f35~=nil then
                s35=f35+1
                c35=s3[f35][1]  -- image pair
                m35=s3[f35][2]  -- mirror of c35
                f33=f35-2
                if f35>8 then
                    if f33<9 then
                        f33=f33+8
                    end
                elseif f33<1 then
                    f33=f33+8
                end
                c33=s3[f33][1]  -- image pair
                m33=s3[f33][2]  -- mirror of c33
            end
        end
    end
    
    function m3347(a)
        if s47>16 then
            f47=nil
        else
            f47=srch(s4,a,s47)
            if f47~=nil then
                s47=f47+1
                c47=s4[f47][1]  -- image pair
                m47=s4[f47][2]  -- mirror of c47
            end
        end
    end
    
    function m2145()
        f45=f47-2
        if f47>8 then
            if f45<9 then
                f45=f45+8
            end
        elseif f45<1 then
            f45=f45+8
        end
        c45=s4[f45][1]  -- image pair
        m45=s4[f45][2]  -- mirror of c45
    end
    
  • Posts: 457

    I've added a link to my code to my explanation post above. For completeness, here it is again.

  • dave1707dave1707 Mod
    Posts: 7,923

    @LoopSpace I like the way you display the disks. Maybe if I keep looking at your code, it’ll start to make sense. But right now it doesn’t. I’ll have to reread your explanation also.

  • Posts: 1,400
    @LoopSpace - very impressive and well annotated. Some aspects of your code are completely new to me. Never seen co-routines used. A lot of learning here for me. Thanks.
Sign In or Register to comment.