Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * - 2 votes

Brain game from computer science


  • Please log in to reply
2 replies to this topic

#1 antipope

antipope

    Newbie

  • Members
  • Pip
  • 3 posts

Posted 08 July 2014 - 02:37 AM

I came up with an idea for a brain game. It's a modification of something called an automaton. Automata theory is a part of theoretical computer science.

 

The game looks like this:

eee.png

 

You can draw those 5 colored edges on a piece of paper and place 2 pawns at the top 2 vertices.

 

The goal is to end up with only 1 pawn.

 

To reach the goal, you can make moves of 3 types, one type for each color, call it C:

When you select color C, you locate every edge with color C such that there is a pawn on one end and there is no pawn on the other end. Let's call these edges C-triggered.

Then you move pawns along C-triggered edges:

- If there is a pawn adjacent to k C-triggered edges, it splits into k pawns.

- If more than one pawn arrives at the same destination, they are merged.

 

In other words, after color C move, every edge that was C-triggered is "swapped"; that is for each end vertex if there was a pawn before, now there isn't and vice versa (note that there is a pawn on exactly one end since edge was C-triggered).

 

Can you solve the problem instance on the picture? What is the minimum number of moves?

 

Spoiler for Hint

 

You can post the answer in the form RRYGYGR..., where R=red, Y=yellow, G=green.


Edited by antipope, 08 July 2014 - 02:39 AM.

  • 0

#2 k-man

k-man

    Advanced Member

  • Members
  • PipPipPip
  • 452 posts
  • Gender:Male

Posted 08 July 2014 - 05:06 PM

Spoiler for solution


  • 1

#3 antipope

antipope

    Newbie

  • Members
  • Pip
  • 3 posts

Posted 08 July 2014 - 09:15 PM

Nice! I wasn't sure if someone would be patient enough to solve this on paper :)

 

For those of you who liked this, there's a game for Android and this is exactly one level from this game. It's called J-Fizo and you can find it on Google Play if you have Android phone or tablet.

If you get to H level, email me at bd@atablash.pl, send me your email address registered with Google Play; I will add you as testers so you can play the rest of the game for free.

Let me know how far you got since I don't think anybody can pass this entire game without brute-force computer approach ;)

 

PS Here's k-man's solution in animated GIF form (in fact it is the minimum possible number of moves):

Spoiler for Solution

 

 


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users