g | x | w | all

Bytes	Lang	Time	Link
029	Haskell + hgl	240723T135106Z	Wheat Wi
048	sed E Validator	220812T162446Z	Jiří
088	Python 3.8 Validator	220812T172456Z	CursorCo
104	Retina 0.8.2	220814T101201Z	Neil
6268	Python	220813T192442Z	loopy wa
045	x8664 machine code	220813T073515Z	m90
124	brainfuck	220813T140251Z	matteo_c
107	C++ gcc	220812T161033Z	matteo_c
032	05AB1E	220812T205628Z	Kevin Cr

Haskell + hgl, 29 bytes

on(ozW ge**)(m<ce)'/''\\'<pxn

Attempt This Online!

Explanation

pxn get all the prefixes
ce '/' count the /s
ce '\\' count the \s
ozW ge all the \ counts are pairwise greater than or equal to the / counts.

Reflection

There should be shorthand for '\\' and "\\" like there is for '\n' and "\n".
Here we are computing cumulative counts of two different characters. I could see this being useful in the future. We might as well implement a shortcut for it. It can also be implemented to be faster than the way I've done it here which is always a plus.

sed `-E` - Validator, 82 61 59 55 48 bytes

:a
s/D(_*)U/\1/
ta
s/_U|D_//
ta
s/__//g
/./cF
cT

Attempt This Online!

Explanation:

First following transformation is applied on the input: \___/ -> ___. This is done repeatedly, till the whole terrain is of following shape: _/_/___\_\_ - rising from start and then falling till end.

Then following substrings are removed: _/ and \_. Now the terrain is of flat shape ____ and it is just checked if the number of _ is even.

sed `-E` - Generator, 115 107 78 72 bytes

:a
s/D(_*)U/\1/
ta
s/D([^_]*)_/\1M/
s/_([^_]*)U/P\1/
ta
s/_/P/
s/_/M/
ta

Attempt This Online!

Python 3.8 - Validator, 92 88 bytes

lambda c,d={1}:1in[d:={g+1-a*2for g in d if g for a in(f in'/_',f in'/')}for f in c][-1]

Try it online!

Python 3.8 - Generator, 115 113 bytes

lambda c,d={1:''}:[d:={g+1-a*2:d[g]+(f=='_')*'+-'[a]for g in d if g for a in(f in'/_',f in'/')}for f in c][-1][1]

Try it online!

Thanks to Kevin Cruijssen, Steffan, and xnor for -6 bytes.

Retina 0.8.2, 104 bytes

+`^(((?<-3>-|/)|(\+|\\))*)((?<8-3>)|((?<3>)))_(((?<-3>_|/)|(?<3>_|\\))*)$(?(3)^)
$1$#5$*+$#8$*-$6
[^-+]

Try it online! Link includes faster test cases. Outputs nothing if there are no flat bits or the input is invalid. Explanation:

+`

Repeat until all the instructions have been generated.

^(((?<-3>-|/)|(\+|\\))*)

Start by matching either - or / (removing from capture group 3 captured in a previous iteration), or either + or \ (capturing into capture group 3), repeating as much as possible, into capture group 1.

((?<8-3>)|((?<3>)))

Either remove from capture group 3 and capture into group 8 or make another capture into capture group 3 and also capture group 5. Then match the flat bit that we're going to create an instruction for, depending on which option was taken.

_(((?<-3>_|/)|(?<3>_|\\))*)

Match _ or / (still removing from capture group 3) or _ or \ (still capturing into capture group 3) as much as possible into capture group 6.

$(?(3)^)

The match needs to reach the end of the string and all of the captures in group 3 must eventually have been removed.

$1$#5$*+$#8$*-$6

Replace the flat bit with the desired instruction, leaving the prefix and suffix unchanged.

[^-+]

Remove anything that isn't an instruction.

Validator only for 29 bytes:

^((?<-2>_|/)|(_|\\))*$(?(2)^)

Try it online! Link includes faster test cases. Explanation: Basically just the last part of the expression from the full program above, treated as a logical match/fail result.

Python, 62 (generator) + 68 (validator) bytes

-1 @Steffan

(
lambda s:((l:=len(s)//2)-(c:=s.count)("A"))*"+"+(l-c("?"))*"-"
,
lambda s,i=1:[min(i:=i+ord(c)%z-1for c in"?"+s)for z in(7,9)]==[0,i]
)

Attempt This Online!

Takes "AH?" for "\_/" to save a few bytes

x86-64 machine code, 45 bytes (validator and generator)

31 D2 6A 01 59 AC 88 C4 B0 2B 9E 7B 13 73 07 FF CA 79 05 AA FF C2 FF C2 9E 75 03 83 C1 02 E2 E5 D1 E9 B0 2D F3 AA 88 0F 19 CA 19 C0 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RSI the address of the input, as a null-terminated byte string; takes in RDI an address at which to place a string, which will be the instructions for the driver if it's possible; and returns in EAX −1 if possible and 0 if impossible.

In assembly:

f:
    xor edx, edx

Set EDX to 0. EDX will keep track of the minimum possible speed at each point.

    push 1; pop rcx

Set ECX to 1. ECX will keep track of the maximum possible speed plus 1 at each point.

repeat:
    lodsb
    mov ah, al

Load a character from the string into AL, advancing the pointer, and then move it into AH.

    mov al, '+'

Set AL to the ASCII code of '+'.

    sahf

Set flags based on the character in AH. Here are the possibilities, with the important bits bolded:

    SZ A P C
NUL 00100000
\   01011100
_   01011111
/   00101111

    jnp done

Jump if PF=0, true here only for the null terminator.

    jnc must_accel

Jump if CF=0, true here only for \.

    dec edx
    jns second_part

(For _ and /) Subtract 1 from EDX (the minimum speed). Jump if the result is nonnegative, in which case we are done with this part. Otherwise...

    stosb

Write + to the output string, advancing the pointer.

    inc edx

Add 1 to EDX. The next instruction adds 1 more, for a net +1.

must_accel:
    inc edx

(For \) Add 1 to EDX.

second_part:
    sahf

Set flags based on the character in AH again (as the inc or dec has overwritten them).

    jnz must_decel

Jump if ZF=0, true here only for /.

    add ecx, 2

(For _ and \) Add 2 to ECX (the maximum speed plus 1); the next instruction will subtract 1, for a net +1.

must_decel:
    loop repeat

(/ jumps here) Subtract 1 from ECX and jump back if the result is nonzero (if the maximum speed did not drop to −1).

done:

If the parcours is possible, the minimum speed is 0, and the maximum speed is 2 times the number of flat pieces that should be decelerated on (because the maximum speed is obtained by accelerating on all of them, and changing one acceleration to a deceleration reduces the final speed by 2).

If it's not possible, either the end of the string has been reached with a nonzero minimum speed, or the loop ended prematurely with the maximum speed becoming −1 from a /, in which case the minimum speed will have changed from 0 to 1 on that /, and thus will also be nonzero.

    shr ecx, 1

Shift ECX (the maximum speed plus 1) right by 1 bit. If the parcours is possible, this produces the number of flat pieces that should be decelerated on.

    mov al, '-'
    rep stosb

Put the character code of - in AL and write it to the output string ECX times, advancing the pointer and counting down ECX.

    mov [rdi], cl

Add the low byte of ECX, which is now 0, to the output string.

    sbb edx, ecx

Subtract ECX+CF from EDX. ECX is still 0. CF is the bit shifted out of ECX previously.

If the parcours is possible, CF will be 1 and EDX 0, so the result will wrap around to all 1s, and CF will be 1 afterwards.

If it's not possible, EDX will be nonzero and CF may be 0 or 1, but either way the result will not wrap around, so CF will be 0 afterwards.

    sbb eax, eax

Subtract EAX+CF from EAX, making it −CF: −1 if possible and 0 if impossible.

ret

Return.

brainfuck, 124 bytes (validator and generator)

,[------->-[<->---]+<[---[>->+>->>+<[->-]>[.->]<<<<<<[-]]>[->+>+<<]<[-]]>[->->+>+<<<]<,]--[>+<++++++]>>[--<.>]<++>>[--<<.>>]

If the parcour is valid, it just outputs the instructions; otherwise, it prints one or more bytes of value 0x01, followed by some instructions (which are of course meaningless).

Try it online!

Note: it works only if the difference in height is always less or equal to 255, counting from the start.

brainfuck, 103 bytes (generator only)

,[------->-[<->---]+<[---[>->+>-<<<[-]]>[->+>+<<]<[-]]>[->->+<<]<,]--[>+<++++++]>>[--<.>]<++>>[--<<.>>]

Try it online!

Note: for both programs, the input must be zero terminated. Both programs works only if the total number of + and - of the output is less than 128.

C++ (gcc), 107 bytes (generator and validator)

g(char*x,int s=0){return*x?*x-47&&g(x+1,s+1)&&(*x=*x-95?32:43)||*x-92&&s&&g(x+1,s-1)&&(*x=*x-95?32:45):!s;}

Try it online!

C++ (gcc), 71 bytes (only validator)

v(char*x,int s=0){return*x?*x-47&&v(x+1,s+1)||*x-92&&s&&v(x+1,s-1):!s;}

Try it online!

Note: in both functions 4 bytes could be saved by replacing the boolean ands and or with bitwise ones, but it would be extremely slow. In the generator, the ands before (*x=*x-95?32:43) and before (*x=*x-95?32:45) must be boolean in any case (otherwise it does not output the correct instructions).

C++ (gcc), 239 bytes (formatter, extra)

#include <cstring>
#include <cstdio>
f(char*x){int*a=new int[strlen(x)+1],i=a[0]=0,m=0,M=0;for(;x[i];++i)a[i+1]=(a[i]+=(x[i]==92))-(x[i]==47),m=a[i]<m?a[i]:m,M=a[i]>M?a[i]:M;for(;m<=M;++m,puts(""))for(i=0;x[i];++i)putchar(a[i]-m?32:x[i]);}

Try it online!

05AB1E, 32 bytes

®1‚„_\Ik©0¢ãʒ0®r.;ηO¤Ā(ªdP}ZÄ=i,

Combines the Validator and Generator programs into a single program to save bytes.

Input as a list of characters.
Outputs an empty string as falsey, or 1 as truthy. In addition, outputs all possible generator outputs as a list of lists of -1/1 for deceleration/acceleration respectively.

Try it online or verify (almost) all test cases. (The larger test cases are omitted; the more _ are in the input, the slower the program becomes because of the ã.)

Explanation:

®1‚          # Push pair [-1,1]
   „_\       # Push string "_\"
      I      # Push the input character-list
       k     # Get the 0-based index of each character in "_\",
             # or -1 if it isn't present (in case of "/")
        ©    # Store this list in variable `®` (without popping)
         0¢  # Count the amount of 0s
           ã # Get the cartesian product of the [-1,1] with this count
             # (resulting in all possible count-sized list of -1s/1s)
ʒ            # Filter this list by:
             #  (implicitly push the current list of -1s/1s
 0           #  Push a 0
  ®          #  Push list `®`
   r         #  Reverse the order of these three
    .;       #  Replace every 0 in list `®` with the -1s/1s of the current list in order
 ηO¤Ā(ªdP    #  Check two things:
             #    1. The sum results in exactly 0
             #    2. No prefix is negative (so we never have any negative m/s speeds)
 η           #   Get the prefixes of this list
  O          #   Sum each inner prefix-list
   ¤         #   Push the last sum (without popping), which is the sum of the full list
    Ā        #   Check if it's NOT 0 (0 if 0; 1 otherwise)
     (       #   Negate it (0 if 0; -1 otherwise)
      ª      #   Append it to the list
       d     #   Check for each inner integer if it's non-negative (>= 0)
        P    #   Check if this is truthy for all of them
}            # Close the filter
             # (we now have a list of all possible paths if truthy; or [] if falsey)
 Z           # Push the flattened maximum (without popping): 1/-1 for truthy; "" for falsey
  Ä          # Get its absolute value: 1 for truthy; "" for falsey
   =         # Output it with trailing newline (without popping)
    i        # And if it was 1:
     ,       #  Also output the list itself on another line

Haskell + hgl, 29 bytes

Explanation

Reflection

sed -E - Validator, 82 61 59 55 48 bytes

sed -E - Generator, 115 107 78 72 bytes

Python 3.8 - Validator, 92 88 bytes

Python 3.8 - Generator, 115 113 bytes

Retina 0.8.2, 104 bytes

Python, 62 (generator) + 68 (validator) bytes

-1 @Steffan

x86-64 machine code, 45 bytes (validator and generator)

brainfuck, 124 bytes (validator and generator)

brainfuck, 103 bytes (generator only)

C++ (gcc), 107 bytes (generator and validator)

C++ (gcc), 71 bytes (only validator)

C++ (gcc), 239 bytes (formatter, extra)

05AB1E, 32 bytes

sed `-E` - Validator, 82 61 59 55 48 bytes

sed `-E` - Generator, 115 107 78 72 bytes