3
\$\begingroup\$

You're tasked with writing an algorithm to efficiently estimate cost of solving an Eni-Puzzle from a scrambled state as follows:

You're given m lists of containing n elements each(representing the rows of the puzzle). The elements are numbers between 0 and n-1 inclusive (representing the colors of tiles). There are exactly m occurrences of each integers across all m lists (one for each list).

For example:

m=3, n=4 :

[[3, 0, 3, 1],            [[1, 3, 0, 1],
 [1, 0, 2, 2],     or      [0, 2, 3, 1],
 [3, 0, 1, 2]]             [0, 3, 2, 2]]

You can manipulate these lists in two ways:

1: Swapping two elements between circularly adjacent indices in (non circularly) adjacent lists. Cost=1.

Ex:

m=3, n=4 :

Legal:
Swap((0,0)(1,1))
Swap((1,0)(2,3)) (circularly adjacent)

Illegal:
Swap((0,0)(0,1)) (same list)
Swap((0,0)(2,1)) (lists are not adjacent)
Swap((0,0)(1,0)) (indices are not circularly adjacent (they're the same)
Swap((0,0)(1,2)) (indices are not circularly adjacent)
  1. Circularly shifting one of the lists (Cost=number of shifts)

Your algorithm must efficiently calculate minimum cost required to manipulate the lists such that the resulting lists are all rotations of each other (meaning the puzzle can be fully solved from this state using only rotation moves) i.e.:

[[0, 1, 2, 3]          [[2, 1, 0, 3]
 [3, 0, 1, 2]    and   [0, 3, 2, 1]
 [1, 2, 3, 0]]         [3, 2, 1, 0]] 

...are both valid final states.

Instead of lists, you may use any data structure(s) of your choice to represent the puzzle, so long as the cost of simulating a valid move (sliding or rotating) on the puzzle with this representation is O(n*m). The setup cost of initializing this data structure can be disregarded.

A winning solution will compute the cost in the lowest asymptotic runtime in terms of m and n. Execution time will be assessed as a tie breaker.

\$\endgroup\$
  • 3
    \$\begingroup\$ Hi and welcome to PPCG :) I think you do not need fastest-code or code-challenge since you only actually specify the winning criterion as the algorithmic speed. Further, I think you should specify if you mean the asymptotic worst case, or average case (best case is not a good idea, for reasons that are hopefully obvious). For future use, we have a sandbox to post challenges to work out issues before you post to the main site. Good luck! \$\endgroup\$ – FryAmTheEggman Apr 4 at 3:26
  • \$\begingroup\$ I edited the tags. Thanks! \$\endgroup\$ – Conor Henry Apr 4 at 3:52
  • 1
    \$\begingroup\$ why not define the winning state as the actual state where they're all lined up? \$\endgroup\$ – Jonah Apr 4 at 14:29
  • \$\begingroup\$ @JonathanAllan Yes. I've edited this to be more clear. \$\endgroup\$ – Conor Henry Apr 4 at 23:33
  • \$\begingroup\$ @Jonah Because The costs I've outlined here are not the actual number of moves required to make equivalent moves on the puzzle. "Swapping" moves have a higher cost. To solve the actual puzzle, you first reach the state I described, or a state that is only one sliding move away. Because my specifications don't allow direct sliding moves (swapping equal indices) like the puzzle does for the blank space, I don't need to consider this latter case. This reduces the problem so that only the two move types I described need to be considered and the concept of a moving "blank space" can be ignored. \$\endgroup\$ – Conor Henry Apr 5 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.