1. Announcing Mekorama on the Web!

    Now anyone can play levels from the forum online, with one click!

    Dismiss Notice
  2. Psst! If you're new here, welcome! Please visit these pages first for information about the forum and Mekorama:

    Welcome! ¡Bienvenido! Selamat datang! Добро пожаловать! Willkommen!
    and
    Everything you want to know about Mekorama

    Dismiss Notice
Meak

NP completeness

I encoded a satisfiability proposition. Help the robot find its way through the maze.

NP completeness
Meak, Feb 19, 2021
    • Rating:
      4/5,
      ridgerunner
      Didn’t understand the “encoded” reference, but i solved the level by logic.
    • Rating:
      4/5,
      Blue Tower
      I won the level before @Timothy Eugene's level.
      Wow, you need to push the slider as hard as you can to move the 3 stacked sliders and unlock the pillars.
      Thanks for sharing @Meak :thumbsup::thumbsup:
    • ridgerunner
      @Blue Tower .. i am not sure I fully understand your method but it seems different from mine
      select the height for each vertical draggable. The horizontal draggable can now easily be slid in to push B.
    • Divya
      How this work
    • Rating:
      4/5,
      delator77
      Easy but fun level...Thanks for sharing @Meak :thumbsup:
    • Rating:
      4/5,
      Neophyte
      A clever implementation.

      The horizontal slider didn't move very smoothly for me. It seems to be the weight of the vertical sliders which makes it hard to move. Maybe its leading Metal Half Pillar could be rotated 90 degrees clockwise (seen from above) to make its movement easier.

      I hope R achieves his sales target. :)
      Meak likes this.
    • MekaSage
      @Meak - It has been a long time since I learned about NP Completeness and satisfiability and I don't remember the details. Is there an (easy) way to explain how it relates to this level?
    • Meak
      @MekaSage sure. This levels encodes the following satisfiability problem:

      (not a or b or not c or not d or e) and
      (not b or not d) and
      (b or c or not d or e) and
      d and
      (b or not d or not e)

      It is known that these satisfiability formulas (is there an assignement such that the above evaluates to true?) is in general an NP-complete problem, meaning it's relatively easy to verify a solution, but it's hard to find one in general.
      Fortunately, here, it's possible to solve it without brute forcing by looking at clauses in the order of an increasing number of inner terms.
    • Rating:
      4/5,
      Sammy 5
      :eek:
      That one took a while with some patience, trial and error and close scrutiny... but finally got it!:thumbsup:
      Meak likes this.
    • MekaSage
      @Meak - somehow I missed your answer earlier. Thanks for explaining!
    There are no comments to display.
  • Category:
    Logic/Puzzle
    Uploaded By:
    Meak
    Date:
    Feb 19, 2021
    View Count:
    976
    Comment Count:
    11

    EXIF Data

    File Size:
    637.5 KB
    Mime Type:
    image/jpeg
    Width:
    1080px
    Height:
    2312px
    Make:
    HUAWEI
    Model:
    MAR-LX3A
    Date / Time:
    2021:02:19 08:26:30
     

    Note: EXIF data is stored on valid file types when a photo is uploaded. The photo may have been manipulated since upload (rotated, flipped, cropped etc).