"Signpost" puzzle from Tatham's collection

Question

Simplified version of "Signpost" puzzle from Simon Tatham's Portable Puzzle Collection.

How the puzzle is created

We pick up randomly positive integer N and one of permutations of 1…N
with 1 at the first position:
N = 12

Numbers 1 and N always stay open, and 2 is always on the right of 1.
So we look at numbers 2 and 3. 3 is on the left from 2, so we mark 2 with left arrow:

Next we look at 3 and 4. 4 is on the right from 3, so we mark 3 with right arrow:

And so on so that every arrow above the number points towards the number that follows it (though the next number can be any distance away in that direction):
After all we hide initial sequence except 1 and N:
and write down puzzle in form of array:

["1", "→", "→", "→", "→", "←", "→", "←", "12", "←", "←", "←"]

Task

Given by an array of directions and two key positions, restore the initial sequence of numbers.

Input

List of directions and keys in any form, suitable for your language: array, json, string etc.
Let for example "→" be "r" and "←" be "l":

["1", "r", "r", "r", "l", "r", "l", "12", "l", "l", "l"]

You may take N as a separate input or calculate it as length of list.
You may assume that key points are given not as numbers,
but as symbols (for example "1" = "b"(egin) and N = "e"(nd) )

Input always valid: non-empty, no typos, errors and necessarily corresponds to some valid sequence.

Output

Encrypted sequence as array, echo-print or as you like.
You may only use test cases that are composed of existing sequences and therefore have at least one solution. But if there may be several, you can print any or all of them.

Test cases

In "r" / "l" / "1" / "N"  form:

["1", "2"] → [1, 2]
["1", "3", "l"] → [1, 3, 2] 
["1", "r", "5", "l", "l"] → [1, 3, 5, 2, 4] or [1, 2, 5, 4, 3]
["1", "r", "6", "r", "r", "l"] → [1, 2, 6, 3, 4, 5]
["1", "r", "r", "r", "r", "l", "r", "l", "12", "l", "l", "l"] → [1, 3, 11, 5, 9, 10, 6, 8, 12, 4, 2, 7]
["1", "7", "l", "l", "l", "l", "l"] → [1, 7, 6, 5, 4, 3, 2]
["1", "r", "r", "l", "7", "l", "l"] → [1, 5, 3, 4, 7, 2, 6] or [1, 6, 4, 5, 7, 3, 2]

Answer 1

Vyxal, 147 bits¹, 18.375 bytes

2€÷ṘN"ƛż*⇧⇧›;÷ṘȮL+?LpJ

Try it Online!

Takes input as single list without the starting symbol where 1 is an arrow to the right, -1 is an arrow to the left and 2 is the end.

Doesn't output the first 1.

How?

Suppose that we have an input like this:

> < > < e < > <

We split the input on the end symbol and in the first part start assigning numbers to the left arrows from right to left.

> < > < e < > <
      1

> < > < e < > <
  2   1

Then assign numbers to the right arrows from left to right.

> < > < e < > <
3 2 4 1

This way the last number in the first part points to the right.

Similarly we can assign numbers to the second part in a way that the last number points to the left.

Code explanation

2€÷ṘN"ƛż*⇧⇧›;÷ṘȮL+?LpJ
2€                     # split on 2
  ÷                    # push each element
   Ṙ                   # reverse
    N                  # times -1
     "                 # pair
      ƛ                # map:
       ż*              #   multiply each by it's 1-based index
         ⇧             #   grade up (sort indices by their value)
          ⇧            #   grade up
           ›           #   increment
            ;          # end map
             ÷         # push each element
              Ṙ        # reverse
               Ȯ       # copy the second to last element on the stack to the top of the stack
                L      # length
                 +     # add
                  ?L   # input length
                    p  # prepend
                     J # join

Answer 2

Charcoal, 38 bytes

≔⌕Ａ…θ⌕θＩＬθrηＥθ⎇№βιＩ⁺²⌕⁺⁺⁻⌕Ａθrη⮌⌕Ａθlηκι

Try it online! Link is to verbose version of code. Explanation:

≔⌕Ａ…θ⌕θＩＬθrη

Find the indices of all of the rs that appear to the left of the ending position.

Ｅθ⎇№βιＩ⁺²⌕⁺⁺⁻⌕Ａθrη⮌⌕Ａθlηκι

Find the indices of all the right rs, concatenate with the reversed indices of all the ls and with the indices of the left rs. Replace each lowercase letter with the index of its index in the list of indices, plus 2.

Answer 3

Jelly, 17 bytes

ẹⱮØ<ṚNƭ€F>ÞMA;MŻỤ

A monadic Link that accepts the signpost array as a list of characters with no leading 1 and with one N mixed with < for left and > for right and yields a possible input permutation.

Try it online!

How?

ẹⱮØ<ṚNƭ€F>ÞMA;MŻỤ - Link: signpost list, S
  Ø<              - "<>"
 Ɱ                - map across (c in "<>") with:
ẹ                 -   indices of (c) in (S)
       €          - for each:
      ƭ           -   alternate between:
    Ṛ             -     a) reverse; and
     N            -     b) negate
        F         - flatten
           M      - maximum indices (of S) -> [index of 'N' in S]
          Þ       - sort (the flattened list) by:
         >        -   is greater than (maximum indices)? (vectorises)
            A     - absolute values
              M   - maximum indices (of S) -> [index of 'N' in S]
             ;    - (absolute values) concatenate (maximum indices)
               Ż  - prepend a zero
                Ụ - sort the indices (of that) by their values

Example

Using S with the leading 1 will also work so long as N>1, it just increases the results of ẹⱮؽ by one with no effect on the final result.

S     "><><>>N><>><":
         >   <   >   <   >   >   N   >   <   >   >   <
M                               [7]
ẹⱮØ<     [[2, 4, 9, 12], [ 1, 3, 5, 6, 8, 10, 11]]
ṚNƭ€     [[12, 9, 4, 2], [-1,-3,-5,-6,-8,-10,-11]]
F        [12,  9,  4,  2, -1, -3, -5, -6, -8,-10,-11]
>ÞM      [ 4,  2, -1, -3, -5, -6, -8,-10,-11, 12,  9]
A        [ 4,  2,  1,  3,  5,  6,  8, 10, 11, 12,  9]
;MŻ   [0,  4,  2,  1,  3,  5,  6,  8, 10, 11, 12,  9, 7] (ie 1st, 5th, 3rd, 2nd, ...)
Ụ     [1,  4,  3,  5,  2,  6,  7, 13,  8, 12,  9, 10, 11]
       1   >   <   >   <   >   >   N   >   <   >   >   <

Answer 4

Python, 154 bytes

lambda x:(z:=len(x))and next(i for i in permutations(range(z))if all(x[j]==i[j]or("RL"[j>i.index(i[j]+1)]==x[j])for j in range(z)))
from itertools import*

Attempt This Online!

0-indexed. I imagine in 5 minutes someone will post a answer in half this number of bytes

Answer 5

Vyxal, 207 bits¹, 25.875 bytes

żṖ'£Lɾḣṫ$⟑›"¥vḟƒ>‛rli;pJn‹İ?⁼

Try it Online!

Probably times out online for anything larger than a 5 item list.

Signpost is my favourite puzzle in the pack btw - the 5x5 grids are what I main. I sometimes do 6x6s for fun, or 4x4s when I want to see how fast I can solve one. It's especially fun when there's no extra hints, just the start, end, and a whole bunch of arrows. Non-fixed start/end positions are fun too :p

Explained

This boils down to "find the first permutation where applying the algorithm gives the input"

żṖ'£Lɾḣṫ$⟑›"¥vḟƒ>‛rli;pJn‹İ?⁼
żṖ'                            # All permutations (P) of the range [1, input.length] where:
   £Lɾḣṫ$                      #   The range [2, P.length)
         ⟑›"¥vḟƒ>‛rli;         #   With the following applied to each item (eagerly evaluated):
          ›"                   #     [item, item + 1]
            ¥vḟ                #     0-indexed positions in P
               ƒ>              #     reduced by greater than
                 ‛rli          #     indexed into the string "rl"
                               #   (This determines which way a number points in P)
                     pJ        #  With 1 prepended and P.length appended
                       n‹İ     #  In the original of order of P
                          ?⁼   #  Equals the input

Answer 6

Wolfram Language (Mathematica), 144 bytes

(m=Max@#;r[a_,i_,n_]:=(If[n >0,MapThread[If[#1<2&&#1(#2-i)<0,r[w=ReplacePart[a,#2->n-1],#2,n-1]]&,{a,Range@m}]];w);r[#,Position[#,m][[1,1]],m])&

Try it online!

Recursive approach. It seems that no one has used it yet.
I’m sure it can be made shorter and better, but so far so.
Take input with:

• First position 0
• Max number N as it is
• Left direction -1
• Right direction 1

Ungolfed explained:

mainRec[arr_, currentInd_, current_] :=
  (If[current > 0,
    MapThread[
     If[#1 < 2 && #1*(#2 - currentInd) < 0,
       (*Recursive call for items that could be predecessors of \
current*)
       mainRec[currentArr = ReplacePart[arr, #2 -> current - 1], #2, 
        current - 1]
       ] &,
     {arr, Range@Length@arr}]
    ]; currentArr);
init = {0, 1, 1, 6, 1, -1};
(*First call with initial puzzle, N and index of N*)
mainRec[init, Position[init, Max@init][[1, 1]], Max@init]