## 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

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

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

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.

jaap
Posts: 2090
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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

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.

Xanthir
My HERO!!!
Posts: 5358
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

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

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

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

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

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.

jaap
Posts: 2090
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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

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?

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.

Xanthir
My HERO!!!
Posts: 5358
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

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

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)))

Flumble
Yes Man
Posts: 2109
Joined: Sun Aug 05, 2012 9:35 pm UTC

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

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. (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?

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.

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

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

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

Xanthir
My HERO!!!
Posts: 5358
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

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

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)))