Go Back   Freethought Forum > The Amphitheater > The Colosseum

Reply
 
Thread Tools Display Modes
  #26  
Old 10-02-2010, 10:10 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

:bump:

Some extra games have been added recently. I like signpost.
Reply With Quote
Thanks, from:
Ensign Steve (10-02-2010), JoeP (10-04-2010)
  #27  
Old 10-03-2010, 10:51 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

Quote:
Originally Posted by Ensign Steve View Post
Okay, I see what you guys mean. I had just been playing the default, 10 points, and it was boringly easy. I just tried it at 25 and had the aha moment. I'm trying it at 50 now. Whee!

Edit: 50 done in 10 minutes. Now trying 100. Whee!

Edit: Shit, you guys! It's too big for my screen. With 50 I had to hide the dock to get to the bottom dots, but at 100 I can't do it at all. :sadcheer: Any suggestions from mac users?

Now I have a mac I see what you mean :sadcheer: I couldn't find any way to resize the window on the mac executable version without using add-on applications.

But if you use the java version that runs in your browser, then you get to see the whole thing. :cheer: Be warned it takes quite a while to generate a custom 250 point untangle.
Reply With Quote
Thanks, from:
Ensign Steve (10-03-2010)
  #28  
Old 10-03-2010, 03:48 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is offline
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXX
Images: 66
Default Re: Simon Tatham's Puzzle Collection

Damn I used to have a lot of icons in my doc. :lol: Remember Mudwalker?
__________________
:kiwf::smurf:
Reply With Quote
  #29  
Old 11-16-2014, 01:14 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

Quote:
Originally Posted by JoeP View Post
How's your untangle algorithm going, cep?
Aha! I came back to this algorithm when I was inspired by a graph representation diagram in the Coursera free on-line Algorithms course I'm taking. It's only been seven years since I last thought about it!

So I've written some code that models (and animates) Untangle as a physical system. The lines connecting the dots represent elastic bands trying to pull the dots closer to each other and I gave all the dots a positive charge so that they repel each other, especially when they get close, and that prevents all the dots from collapsing together into a black hole due to the elastic attractive forces.

Oh and I added some viscosity too, so the points don't just twang into position but move fairly smoothly - as though they are being dragged through treacle.

I started out with Hooke's law for the spring forces (force proportional to length) but I experimented and found it works best when the force is proportional to length cubed. I've kept the repulsion force using the standard Coulomb's law (inverse-square).

It works pretty great and smoothly at Untangling up to a few hundred points, but gets a bit slow and stuttery after that. It's very interesting to watch it working - although I am of course biased, being the proud author!

It sometimes solves the puzzle completely just using the model described above, but more often it gets stuck with just a few crossing lines around the outside edge. I found that at that stage (when the initial movements cease) the program can automatically freeze some of the outer points (that form a loop) in position and then remove all the repulsion forces - and the last few crossing points are then eliminated as the tension takes over.
__________________

Last edited by ceptimus; 11-16-2014 at 01:27 AM.
Reply With Quote
Thanks, from:
Dragar (11-16-2014), Ensign Steve (11-22-2014), JoeP (11-16-2014), lisarea (11-16-2014)
  #30  
Old 11-16-2014, 03:50 AM
lisarea's Avatar
lisarea lisarea is offline
Solitary, poor, nasty, brutish, and short
 
Join Date: Jul 2004
Posts: XVMMMDCXLII
Blog Entries: 1
Images: 3
Default Re: Simon Tatham's Puzzle Collection

Weird. I just installed the Android version yesterday. I was thinking about it, and I checked to see if anyone had made it into an app, and someone had.

PS There is an Android app of Simon Tatham's puzzle collection, for anyone who wants to play the games instead of just cheating like that old lazybones ceptimus.
Reply With Quote
Thanks, from:
ceptimus (11-16-2014), Crumb (11-16-2014), Ensign Steve (11-22-2014), JoeP (11-16-2014), Stormlight (03-29-2016)
  #31  
Old 11-16-2014, 10:09 AM
JoeP's Avatar
JoeP JoeP is online now
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Simon Tatham's Puzzle Collection

Quote:
Originally Posted by ceptimus View Post
Quote:
Originally Posted by JoeP View Post
How's your untangle algorithm going, cep?
So I've written some code that models (and animates) Untangle as a physical system. The lines connecting the dots represent elastic bands trying to pull the dots closer to each other and I gave all the dots a positive charge so that they repel each other, especially when they get close, and that prevents all the dots from collapsing together into a black hole due to the elastic attractive forces.

Oh and I added some viscosity too, so the points don't just twang into position but move fairly smoothly - as though they are being dragged through treacle.

I started out with Hooke's law for the spring forces (force proportional to length) but I experimented and found it works best when the force is proportional to length cubed. I've kept the repulsion force using the standard Coulomb's law (inverse-square).

It works pretty great and smoothly at Untangling up to a few hundred points, but gets a bit slow and stuttery after that. It's very interesting to watch it working - although I am of course biased, being the proud author!

It sometimes solves the puzzle completely just using the model described above, but more often it gets stuck with just a few crossing lines around the outside edge. I found that at that stage (when the initial movements cease) the program can automatically freeze some of the outer points (that form a loop) in position and then remove all the repulsion forces - and the last few crossing points are then eliminated as the tension takes over.
This post is useless without a flash animation.
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
Thanks, from:
ceptimus (11-16-2014), Ensign Steve (11-22-2014)
  #32  
Old 11-16-2014, 10:19 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

While I was looking at Untangle again, I followed Simon's documentation back to the 'original' version named Planarity and written by John Tantalo. It's a bit different to Untangle in that it presents you with levels of increasing difficulty and awards you points based on how fast you solve each level. And it's up to you to decide when a level is untangled - you have to click on the 'done' button rather than having the program auto-detect when the puzzle is solved.

Play Planarity in your browser by clicking this link.

Also at that site there are a couple of versions for iPhone - which I've not tried.
__________________
Reply With Quote
Thanks, from:
lisarea (11-16-2014)
  #33  
Old 11-16-2014, 10:23 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

Quote:
Originally Posted by JoeP View Post
This post is useless without a flash animation.
Redoing it in Flash would be a lot of work - and Flash seems to be dying out now that phones and tablets don't support it.

I'll capture the output in an animated gif and post that.

The program is written in Java. I'll look at putting that on-line once I've tidied up the code a little.

ETA:

__________________

Last edited by ceptimus; 11-16-2014 at 11:09 AM.
Reply With Quote
Thanks, from:
Crumb (11-16-2014), JoeP (11-16-2014), lisarea (11-16-2014), SR71 (11-17-2014)
  #34  
Old 11-22-2014, 04:56 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

I tweaked the algorithm a bit. Maybe it doesn't look as interesting now, but it gets the job done - even with large puzzles - and it's a very simple algorithm to implement manually, as described below.


  1. Find ANY "face". If you're doing it by hand then any triangle will do, but I made the program choose one of the largest faces.
  2. Put the points of the chosen face (triangle) at the outside. From now on, never move those points.
  3. Move any point towards where its connected lines would pull it if they were elastic bands.
  4. Chose a different point and repeat step 4 till no lines cross. The program just chooses all the points in turn, but if you're doing it manually, then you can choose one of the points with the longest connecting lines.

It's interesting that once the puzzle is solved any enclosed space (what I call a 'face') can be on the outside - imagine sliding the puzzle onto a sphere, and sliding it around - on a sphere you can then get any face to be the outside without ever crossing a line.

Since a triangle is always a triangle then it's easy to find one when the puzzle is in its messed up state - but if you try to find quadilateral or pentagon or whatever when the puzzle isn't solved, you're likely to chose one that isn't really a face - because it has triangles or other smaller polygons inscribed within it, It's not easy to spot that when the puzzle is messed up - but the program uses a fancy algorithm to do it.
__________________
Reply With Quote
Thanks, from:
Crumb (11-22-2014), Ensign Steve (11-22-2014), JoeP (11-22-2014), lisarea (11-22-2014)
  #35  
Old 11-22-2014, 07:42 PM
Ensign Steve's Avatar
Ensign Steve Ensign Steve is offline
California Sober
 
Join Date: Jul 2004
Location: Silicon Valley
Gender: Bender
Posts: XXXMMCXX
Images: 66
Default Re: Simon Tatham's Puzzle Collection

So the reason your final solved image looks like a big circle (or 15-ish-sided regular polygon) is that your program starts with the largest face? If it started with a triangle, the final image would be shaped like a triangle on the outside, yes? Cool

What do you use to draw the graphs? I downloaded JUNG but I'm not enamored with it. It has way more bells and whistles than I need. I feel like trying to cobble something out using plain old Graphics2D.
__________________
:kiwf::smurf:
Reply With Quote
  #36  
Old 11-22-2014, 09:41 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

Quote:
Originally Posted by Ensign Steve View Post
So the reason your final solved image looks like a big circle (or 15-ish-sided regular polygon) is that your program starts with the largest face? If it started with a triangle, the final image would be shaped like a triangle on the outside, yes?
Yes, spot on.

Quote:
What do you use to draw the graphs? I downloaded JUNG but I'm not enamored with it. It has way more bells and whistles than I need. I feel like trying to cobble something out using plain old Graphics2D.
I've been using the simple Java graphics library written by Professor Sedgewick and his colleagues and recommended for us to use on his Algorithms course. It's really just a simple wrapper around the more standard Java graphics library - but it's great to use for stuff like this as it hides away unnecessary details and lets you just get on with drawing.
There are also simple Java libraries for reading from files and standard input, formatting output, playing sounds and music - all free and you can also browse and modify the source code if you wish.

Take a look at the so-called 'booksite' for Sedgewick's Algorithm course. Click on 'Code' and then scroll down till you see StdDraw.java There are instructions there on how to set up an environment where everything you need is included in the classpath - so all the functions are available as if they were built-in to Java - you don't even need to put "import blah.blah" in your source code to use it.
__________________
Reply With Quote
Thanks, from:
Ensign Steve (11-22-2014)
  #37  
Old 12-09-2014, 08:29 AM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

I've been playing Loopy from the collection lately - like untangle and some of the other puzzles in the collection it's really (in algorithms terms) a graph processing problem - but it's nicely packaged up as a puzzle. Try a few of the simple 'square' puzzles but once you get the hang of those be sure to move on to the puzzles based on triangular and hexagonal and other networks which are much more fun and interesting.
__________________

Last edited by ceptimus; 12-09-2014 at 09:02 AM.
Reply With Quote
Thanks, from:
Ensign Steve (12-09-2014), lisarea (12-09-2014)
  #38  
Old 04-19-2015, 10:44 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

There's a new game of laying railroad tracks that's been added to the collection. As always, you can increase the difficulty once you get the hang of the simple version of the puzzle.

http://www.chiark.greenend.org.uk/~s...cks.html#8x8de
__________________
Reply With Quote
Thanks, from:
BrotherMan (04-20-2015), Crumb (04-20-2015), Janet (04-25-2015), JoeP (04-19-2015), lisarea (04-19-2015)
  #39  
Old 12-10-2015, 01:53 PM
JoeP's Avatar
JoeP JoeP is online now
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Simon Tatham's Puzzle Collection

Bump.

The GCHQ have posted a Christmas puzzle which is a large (25x25) version of Pattern, from Simon Tatham's Portable Puzzle Collection:


As reported in Can you solve GCHQ's Christmas card puzzle? - BBC News - it's a cryptic Christmas card, a baffling brainteaser:


The GCHQ link http://www.gchq.gov.uk/press_and_med...zzle-2015.aspx is currently down. Perhaps that's part of the puzzle ...

I haven't started it yet.
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
Thanks, from:
BrotherMan (12-10-2015), ceptimus (12-10-2015), Crumb (12-10-2015), Janet (12-10-2015), lisarea (12-10-2015)
  #40  
Old 12-10-2015, 04:52 PM
JoeP's Avatar
JoeP JoeP is online now
Solipsist
 
Join Date: Jul 2004
Location: Kolmannessa kerroksessa
Gender: Male
Posts: XXXVMMXI
Images: 18
Default Re: Simon Tatham's Puzzle Collection

Having filled in some I suddenly realised it's almost certainly going to result in a QR code image, linking to the next stage of the puzzle.
__________________

:roadrun:
Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:   :finland:
Reply With Quote
Thanks, from:
BrotherMan (12-10-2015), ceptimus (12-10-2015), Janet (12-10-2015)
  #41  
Old 01-28-2016, 04:18 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

Only a couple of days left for someone to win the GCHQ puzzle prize.

About 30,000 people followed the QR code to stage 2 of the puzzle, and just a few people have reached the final stage 5 page:

http://www.gchq.gov.uk/58aa7ef96f305...ges/index.aspx

You have to email your answers to the questions on that page. GCHQ say that if no one gets all the answers right then they'll draw the winner from all those who obtain the same, highest, score.
__________________
Reply With Quote
Thanks, from:
JoeP (01-28-2016), lisarea (01-28-2016)
  #42  
Old 02-04-2016, 11:39 PM
ceptimus's Avatar
ceptimus ceptimus is offline
puzzler
 
Join Date: Aug 2004
Location: UK
Posts: XVMMDCCLXXXIX
Images: 28
Default Re: Simon Tatham's Puzzle Collection

GCHQ Christmas card puzzle winners announced - BBC News

There were three winners.

Quote:
They [each] win a GCHQ paperweight, a pen and a signed copy of Alan Turing Decoded, by Turing's nephew Dermot Turing.
They must have put in an awful lot of work to win those feeble prizes, but I suppose solving the puzzles and the excitement of the competition was their main reward.
__________________
Reply With Quote
Thanks, from:
BrotherMan (02-05-2016), Crumb (02-04-2016), JoeP (02-07-2016), slimshady2357 (02-05-2016)
Reply

  Freethought Forum > The Amphitheater > The Colosseum


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

 

All times are GMT +1. The time now is 01:01 PM.


Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Page generated in 0.43312 seconds with 15 queries