Reconstructing a tiling from "is-adjacent-to" data?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Envelope Generator
Posts: 581
Joined: Sat Mar 03, 2012 8:07 am UTC
Location: pareidolia

Reconstructing a tiling from "is-adjacent-to" data?

Postby Envelope Generator » Tue Nov 10, 2015 5:24 pm UTC

I was idly Wikisurfing, trying to navigate through a province county by county by clicking through listings of neighboring counties on the Wikipedia pages of individual counties, and this popped into my head: is reconstructing a tiling (I'm not sure if that's the right word) from a set of "X is adjacent to Y" data a known problem? How hard is it?
I'm going to step off the LEM now... here we are, Pismo Beach and all the clams we can eat

eSOANEM wrote:If Fonzie's on the order of 100 zeptokelvin, I think he has bigger problems than difracting through doors.

User avatar
jaap
Posts: 2072
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby jaap » Tue Nov 10, 2015 6:23 pm UTC

You can think of this data as a graph, where the countries are vertices and the 'is adjacent to' relation gives you the edges.
Your question then boils down to this: Given a planar graph, draw it without any crossing edges. Or in more mathematical terms, find an embedding of a planar graph in the plane.
According to this wiki page it's of linear time complexity (in the number of edges). Determining whether a graph is planar or not is therefore also linear time.

User avatar
Xanthir
My HERO!!!
Posts: 5215
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby Xanthir » Thu Nov 12, 2015 12:25 am UTC

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Envelope Generator
Posts: 581
Joined: Sat Mar 03, 2012 8:07 am UTC
Location: pareidolia

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby Envelope Generator » Thu Nov 12, 2015 9:10 am UTC

Cool, thanks!
I'm going to step off the LEM now... here we are, Pismo Beach and all the clams we can eat

eSOANEM wrote:If Fonzie's on the order of 100 zeptokelvin, I think he has bigger problems than difracting through doors.

User avatar
jaap
Posts: 2072
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby jaap » Thu Nov 12, 2015 9:31 am UTC

By the way, the solution is usually not unique. For example, if you have 4 countries where each is adjacent to all three others, then you can draw a map in 8 distinct ways: You can choose any of the 4 countries to be in the middle, landlocked by the other three countries, and those other three can be in arranged in two different ways around it which are mirror images of one another.

Edit: Even if you specify which countries have a coast line (essentially adding an extra "country" representing the oceans), then there can still be different ways of drawing a map, beyond just mirror images.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby troyp » Thu Nov 12, 2015 5:17 pm UTC

Xanthir wrote:It's also an enjoyable puzzle game.

That's actually a lot easier than it looks (I guess that's not surprising if it's a linear time algorithm). There's something oddly satisfying about it, though.

User avatar
Xanthir
My HERO!!!
Posts: 5215
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby Xanthir » Fri Nov 13, 2015 5:14 pm UTC

Yeah, it's simple, but has a great "organizing things" feel to it.

(Try all the other games at his site - he just took a bunch of games he liked from the web or random OSes and recoded them in JS for his own use. I'm in love with Towers right now.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby Flumble » Fri Nov 13, 2015 11:34 pm UTC

Xanthir wrote:(Try all the other games at his site - he just took a bunch of games he liked from the web or random OSes and recoded them in JS for his own use. I'm in love with Towers right now.)

This needs a tvtropes-tier warning. I've probably sunk as much time into that site as into minecraft. :oops: (mostly Loopy)

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby troyp » Tue Nov 17, 2015 2:04 am UTC

I've bookmarked the site to check out the other games later. (Actually, I'm sure I've come across this site before, a couple of times. I remember the name.)

It's pretty cool that he's compiled the same C code to Java applets, Javascript and native code on 3 platforms.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby Wildcard » Sun Jan 10, 2016 3:39 pm UTC

Flumble wrote:
Xanthir wrote:(Try all the other games at his site - he just took a bunch of games he liked from the web or random OSes and recoded them in JS for his own use. I'm in love with Towers right now.)

This needs a tvtropes-tier warning. I've probably sunk as much time into that site as into minecraft. :oops: (mostly Loopy)

Undead. For some reason it's really tricky to reason correctly about it for me. For instance, try this puzzle, which I finally resorted to sketching out the two different possibilities to see which one worked.

EDIT: Actually, once you realize that zombies are almost always the last to get filled in, it's often much easier.
There's no such thing as a funny sig.

User avatar
Xanthir
My HERO!!!
Posts: 5215
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Reconstructing a tiling from "is-adjacent-to" data?

Postby Xanthir » Wed Jan 13, 2016 5:48 am UTC

Eh, I fill in everybody together. That particular puzzle was relatively difficult, but I was able to get it done without backtracking, just holding a few relationships in my mind at once. Are you familiar with clicking on the numbers to turn them gray and indicate you've solved their paths? It makes it a lot easier to think about things.

0s are manna from heaven - they dictate *precisely* what everything is along their path - ghosts before the first mirror, vamps after. Numbers equal to the path length are valuable, too - they constrain the before/after first mirror parts to v/z and g/z respectively, and the number on the other side dictates how many zombies (or between-two-mirrors ghosts) there must be. Any path that starts with a mirror is great (or has its first mirror on its last square), too, because that limits you significantly in what possibilities there are. In general, the difference between the numbers on either end of a path give you really valuable information - the larger the difference between the two, the small number of zombies are possible on the path, which might quickly dictate the rest of the positions as definitely ghosts or vampires.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests