Weekend Prorgamming Challenge – Week #42 – No-Lift-Pen Drawings


Image

We all know this game where you draw figure on paper without lifting up your pen and without going through same segment twice.

For instance such drawings are fig.1 and fig.2 the red dot is where you start the drawing with the pen, the blue dot is where you end.

Some drawings can’t be drawn this way, for example fig.3

Problem:

Write code which enters N segments with their coordinates X1,Y1,X2,Y2 then check if it’s possible to draw all segments without lifting your pen and if YES write the path sequence.

The rules:

You can code the solution in any programming language during the weekend and have to submit it to info@olimex.com latest on Sunday February 9th.

On Monday we will upload the solutions on GitHub https://github.com/OLIMEX/WPC

You can play with your real name or with nick if you want to be anonymous, we will not disclosure your personal info if you do not want to.

5 Comments (+add yours?)

  1. Dylan
    Feb 07, 2014 @ 19:27:14

    Week 1 of https://class.coursera.org/algs4partI-004 could be used to help solve this; week 2 will be released shortly and https://class.coursera.org/aofa-002 might also be of interest.

    Reply

  2. WallaceIT
    Feb 09, 2014 @ 01:10:47

    Can a single point be touched more than once?

    Reply

  3. Sergey
    Feb 10, 2014 @ 23:09:19

    “Official” O(N) solution is: https://en.wikipedia.org/wiki/Eulerian_path

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: