Problem of the Day
A new programming or logic puzzle every Mon-Fri

Comments:

• Akshay Bist - 9 years ago

  Start with a room at either end, and move to the next room each day. Since the princess can only move to an adjacent room, the prince is bound to run into her.

  reply permalink

• David - 9 years ago

  Disproof by counter example.
  If your run this a couple times, you will find the princess is not always found, which is the goal of the problem.

  import random
  
  def move_princess():
      direction = int(random.random()*10%2)
      old_room = rooms.index("princess")
      if(0 == old_room):
          direction = 1
      if(16 == old_room):
          direction = 0
      new_room = old_room + (-1)**direction * -1
      rooms[new_room] = "princess"
      rooms[old_room] = "empty"
  
  
  rooms = ["empty" for x in range(17)]
  
  princess_start = int(random.random()*100%17)
  print princess_start
  
  rooms[princess_start] = "princess"
  
  print rooms
  
  for prince in range(30):
      if(rooms.index("princess") == prince):
          print "Consecutive Room Strategy Succeeded."
          break
      move_princess()
  

  reply permalink

• Heroka - 9 years ago

  Choose one room, demand entrance to it every day. The princess has to stay in it once.

  reply permalink

• David - 9 years ago

  What if you choose room 1 and the princess decides to stay in rooms 3 and 4 back and forth?

  reply permalink

• beverku - 9 years ago

  Start at the second room from the left, demand entrance to that room the first and second days, then move sequentially to the right, checking each room for two successive days.

  This ensures that the Princess cannot jump over the Prince, if you went one room / one day.

  By moving sequentially through the rooms it solves the problem of the Princess just swapping back and forth between two rooms, if we checked the same room every day.

  By starting at the second room from the left, and eliminating the final room (because each room is checked two days and the Princess can't stay in it) It leaves 15 rooms to Check at 2 days each. Thus we can guarantee to find the Princess in 30 Days.

  reply permalink

• k4rtik - 9 years ago

  Wow, this does seem like the correct solution. There is a reason between the relationship between the two numbers given: (17-2)*2 = 30, I should have thought about it before coming here for ideas.

  reply permalink

• jim - 9 years ago

  Wouldn't work. If the princess starts in room 4 and the prince asks to see room 2 on day 1, the next day the princess can move to room 3 while the prince still demands to see room 2. Day 3 the princess could move to room 2 and the prince would ask to see room 3.

  reply permalink

• jim - 9 years ago

  ... unless what is meant by demand admittance is to stay the night in that room

  reply permalink

• Tim at DataRobot - 9 years ago

  The answer stumbled across me while I was working out a simplified version of the problem. Let's start with a 5 room version, and we'll extrapolate from there.

  And to make things even easier, assume for a moment that you know the princess started in an odd numbered room.

  Day 1 you'd start in room #1, and if the princess is nowhere to be found, she would have to be in room 3 or 5.

  You'd know that for day 2 she'd have to move from an odd numbered room into an even one, and then on odd days she'd move back into an odd numbered room. Each room only has opposite types next to it, so you know that on even numbered days (like day 2 and day 4), the princess (if she started in an odd numbered room) would have to be in room #2 or #4 (and even number).

  So you can then eliminate possibilities moving down the stream of rooms. Day 1 you'd start on room 1, and move to the right to room #2 on day 2. This would limit her travel to room #1, an already checked odd room, and would mean that on day 3 she'd be again limited to odd numbered rooms.

  Continuing to the right, you'd then check room #3 on day 3, room 4 on day 4, and, knowing she has to be in room 5, you could just wait her out in room #4 on your 5th day.

  Now, we didn't actually know she was an in even numbered room, we guessed and there was a fair chance she wasn't in an odd numbered room to start.

  Fortunately, the same logic applies to the princess if she started in an even numbered room- you can know for sure every odd day she'll be back in an even numbered room, and on even days she has to travel between them.

  You being on room 4 on the 5th day allows you to mark room 4 off of your list, and you can start walking back across the board knowing for sure that your princess is awaiting for you in room 2.

  For 5 rooms this process would take 4 days to cross to room 4 and wait there, then 5 minus 3 days to return back to room #2, which is 5-1 + 5-3, or 6 days.

  For 17 rooms, that's 17-1 + 17-3, or 30 days.

  reply permalink

• Tim at DataRobot - 9 years ago

  Unfortunately, I counted the 4th room three times instead of twice, so a walk across the board would take 4 days to cross, 1 day to sit on the 4th room, and 2 days to return, which adds to 7 days.

  To use this strategy on 17 rooms would take 31 days, unless there's an odd zero indexing situation which no one would like.

  reply permalink

• Tim at DataRobot - 9 years ago

  Aha! Use the same strategy, but assume even numbered rooms at first. That way you only have total-2 rooms to walk on the first pass, and total-2 rooms to walk on the way back.

  30 days!

  reply permalink

• (optional) - 9 years ago

  If you check the room from left to right moving one room every day, you cannot miss the princess if you both start on even numbers or odd numbers (but not when one is even and one is odd). The principle is then move from one end to another and if you miss the princess, it means the princess starts from opposite faction of you. So, change the polarity of your checks (if you start from #2, check #16 twice) and move back to the left one room each day. Starting from #2 is beneficial because it is the first even number (as opposed to #1 being first odd number) and if the prince doesn't meet the princess on first run, it means the princess must have started from odd number.

  reply permalink