5
$\begingroup$

This puzzle serves as the more concrete sequel to my previous post; in particular, see that post for the rules of the game. Rather than (implicitly) demanding a description of a polynomial-time algorithm for solving all such puzzles—an answer I myself didn't/still don't have—this post has a smaller, well-defined scope: Which of the three arrow sequences below are admissible, and which are inadmissible?

  1. ↑↓↓←↑↓←↑↓↓←↑→←→↓↑↑↓→↑↓←↑↓↓↑←↑↓
  2. →↓↓↑→↓↑→↓↓↑↓↑→↑↓↓↑→↑↓←↓↑↑↓←→←→←↑
  3. ↓↓↑↓↓↓↓→←→↓↑↓↓←→←→↓↓→↓↑←→↓↓↓↓↓→←→↓↓→←↓↓→

These puzzles are meant to be analyzed by hand (in particular, I solved them by hand with less than a single sheet of scrap paper each), and any solutions should be human-derivable and human-checkable. I made them of such a size that a brute force algorithm I coded fails to be feasible at about the ~25 arrow size and only gets exponentially worse from there (the above are of size 30, 32, and 40), but I'll hedge my bets that someone might have better hardware or more efficient implementation and so add the no-computers tag (but feel free to use computers to try to understand the problem in general!).

Here are some example sequences that may be useful for practice before tackling the big ones up above:

  1. ↑↑→→
  2. ←↑↑→
  3. ↑→↑↓←↓
  4. ↑←←↑↓→→↓→↑↓←
  5. ↑→↓←↑→↓←
  6. ↑→↑←↑←→↓→
  7. →←→↓→→←←←→↑←

Concerning the three big sequences that officially comprise this puzzle, it may happen that they are first figured out by different posters. In that case, I will accept whoever's answer attains the most points according to the scheme (1) = 30 points, (2) = 32 points, (3) = 40 points.

$\endgroup$
2
$\begingroup$

Sequence 1:

Admissible

enter image description here

Sequence 3:

Not Admissible

enter image description here

We can look at a specific chunk of the sequence, n this case →↓↑↓↓←, and if it cannot be drawn, the entire sequence is not admissible. The top image shows how the first couple of directions must happen. Below it are the two scenarios depending on whether the blue segment begins going to the left or right. Either way, it leads to not being able to go left for its sixth move, making the sequence not admissible.

$\endgroup$
3
  • $\begingroup$ Well done. Although you didn't get the second sequence, since you answered two out of the three problems first, as promised by the post, I'll award you the accepted answer status. I actually had a totally different way of dismissing the third sequence. $\endgroup$ – Feryll May 2 at 22:21
  • $\begingroup$ Also, any word on how you managed to identify these individually impossible subsequences? $\endgroup$ – Feryll May 2 at 22:31
  • $\begingroup$ Essentially I just drew out sequence 3, and although there was occasional bifurcation, for most arrows there was only one way to do it. When I came to some point where the line could not continue, I isolated that chunk of the sequence to see if it was itself impossible and came to the above conclusion about sequence 3. $\endgroup$ – SeptaCube May 3 at 2:17
2
$\begingroup$

My solution(s)

Of the 3 sequences, only 1 is admissible
enter image description here

Since I was confused myself about the correctness, I 'stole' the coloring of the other solution
enter image description here

This is how I did it

enter image description here

$\endgroup$
4
  • $\begingroup$ Nicely done. Mind explaining what those two graphs are indicating? Or how it is that you got the admissible sequence's diagram while still being confused about the correctness? I'd be curious to hear about your methods in general and how closely they line up with my own. $\endgroup$ – Feryll May 2 at 22:20
  • $\begingroup$ Graphs: Subsequences have to stay in each others 'bandwidth', so can differ 1 in how much they drop the same distance further right: Going 1 to the right 3green drops 3 more (drops 5) than 3red (drops 2), so would cross green lines that start lower (1 starts in each tile). Similarly there is a difference of 2 drops (-1 vs +1) when 2red and 2 blue move 2 tiles to the right. $\endgroup$ – Retudin May 3 at 9:25
  • $\begingroup$ Correctness: when looking at the other solution, the differences made me double check my solution and I lost track of where I was (and for a moment I thought I made a mistake). Adding colors helped me see that my solution was also correct, and the now made colored one seemed a useful addition to to my answer $\endgroup$ – Retudin May 3 at 9:30
  • $\begingroup$ Ah, thank you very much for the clarifications. Your diagramming is interesting. $\endgroup$ – Feryll May 3 at 18:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.