Sorting Balls and Water: Equivalence and Computational Complexity

Authors Takehiro Ito , Jun Kawahara , Shin-ichi Minato , Yota Otachi , Toshiki Saitoh , Akira Suzuki , Ryuhei Uehara , Takeaki Uno, Katsuhisa Yamanaka , Ryo Yoshinaka



PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.16.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Japan
Jun Kawahara
  • Kyoto University, Japan
Shin-ichi Minato
  • Kyoto University, Japan
Yota Otachi
  • Nagoya University, Japan
Toshiki Saitoh
  • Kyushu Institute of Technology, Japan
Akira Suzuki
  • Graduate School of Information Sciences, Tohoku University, Japan
Ryuhei Uehara
  • Japan Advanced Institute of Science and Technology, Ishikawa, Japan
Takeaki Uno
  • National Institute of Informatics, Tokyo, Japan
Katsuhisa Yamanaka
  • Iwate University, Japan
Ryo Yoshinaka
  • Graduate School of Information Sciences, Tohoku University, Japan

Cite AsGet BibTex

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka. Sorting Balls and Water: Equivalence and Computational Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.16

Abstract

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP . We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Ball sort puzzle
  • recreational mathematics
  • sorting pairs in bins
  • water sort puzzle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Michael R. Garey and David S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, 1979. Google Scholar
  2. William H. Gates and Christos H. Papadimitriou. Bounds for sorting by prefix reversal. Discret. Math., 27(1):47-57, 1979. URL: https://doi.org/10.1016/0012-365X(79)90068-2.
  3. R. A. Hearn and E. D. Demaine. Games, Puzzles, and Computation. A K Peters Ltd., 2009. Google Scholar
  4. Hiro Ito, Junichi Teruyama, and Yuichi Yoshida. An almost optimal algorithm for Winkler’s sorting pairs in bins. Progress in Informatics, 9:3-7, 2012. Google Scholar
  5. Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412:1054-1065, 2011. Google Scholar
  6. Donald E. Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley Publishing Company, 2nd edition, 1998. Google Scholar
  7. Peter Winkler. Mathematical puzzles: A Connoisseur’s collection, volume 143, pages 149-151. A K Peters, 2004. Google Scholar
  8. Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada. Efficient Enumeration of All Ladder Lotteries and Its Application. Theoretical Computer Science, 411:1714-1722, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail