92
\$\begingroup\$

Write a program that takes a single line string that you can assume will only contain the characters /\_‾. (That's forward and backward slash, underline and overline. You can use ~ in place of overline if you need since overline is not convenient ASCII.)

For example, one possible input is:

__/‾‾\/\_/‾

Your program needs to output a truthy or falsy value depending on whether the left edge of the string is "connected", so to speak, to the right edge of the string via the lines of the characters. So, if the kerning was a bit less, there would be a solid black (albeit kinky) line all the way from the left edge to the right, like an unbroken piece of string or twine.

The output for the above example would be true because the edges are connected:

example path

To be clear on the connections:

  • / connects on its bottom left and top right
  • \ connects on its top left and bottom right
  • _ connects on its bottom left and bottom right
  • (or ~) connects on its top left and top right

Also:

  • It doesn't matter whether the edges of the string started on the top or the bottom, it only matters that they connect horizontally through the whole length of the string.

  • You can assume the input string is non-empty, and of course just one line.

Here are some more examples followed by 1 (truthy) if they are connected or 0 (falsy) if not:

__/‾‾\/\_/‾
1

_
1

\
1

/
1

‾
1

___
1

\/
1

/\/
1

/\/\
1

‾‾‾
1

\\
0

‾‾
1

_‾
0

‾_
0

\_____/
1

\/\\/\\___
0

\/\__/‾‾\
1

______/\_____
1

‾‾‾‾‾‾\\_____
0

‾‾‾‾‾‾\______
1

_____/‾‾‾‾‾
1

\___/‾‾‾\___/‾‾‾
1

\_/_\_
0

\_/\_
1

/\/\/\/\/\/\/\/\/\/\/\/
1

____________________
1

‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
1

‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾/
0

‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾\
1

/\‾/\‾___/\_\/__\/\‾‾
0

The shortest code is the winner.

\$\endgroup\$
  • 37
    \$\begingroup\$ Welcome to PPCG! Nice first challenge. \$\endgroup\$ – AdmBorkBork Mar 18 at 15:30
  • 1
    \$\begingroup\$ Are the characters specified in your challenge the only ones that will appear in the string? \$\endgroup\$ – Embodiment of Ignorance Mar 18 at 15:31
  • \$\begingroup\$ @EmbodimentofIgnorance Yes, only the 4. \$\endgroup\$ – Discrete Games Mar 18 at 15:34
  • 30
    \$\begingroup\$ Wait you could make a language out of this \$\endgroup\$ – Delioth Mar 18 at 18:57
  • 2
    \$\begingroup\$ @Arnauld No, I really think only truthy for connected and falsy for unconnected. (Unless allowing a swap is normal for this kind of question?) \$\endgroup\$ – Discrete Games Mar 19 at 4:35

33 Answers 33

34
\$\begingroup\$

Jelly, 9 bytes

-1 byte thanks to @EriktheOutgolfer

Expect ~ instead of . Returns \$0\$ or \$1\$.

O*Ɲ:⁽8ƇḂẠ

Try it online!, Truthy test suite, Falsy test suite

Using this formula (but otherwise similar to the 11-byte version below):

$$n=\left\lfloor\frac{x^y}{15145}\right\rfloor$$

The transition is valid if \$n\$ is odd, or invalid if \$n\$ is even.

Commented

O*Ɲ:⁽8ƇḂẠ     - main link, taking a string          e.g. "\_/"
O             - get ASCII codes                     -->  [92, 95, 47]
 *Ɲ           - exponentiation on all pairs         -->  [92**95, 95**47]
   :⁽8Ƈ       - integer division by 15145           -->  [23964828…8421, 59257069…0485]
       Ḃ      - least significant bit (i.e. parity) -->  [1, 1]
        Ạ     - all values equal to 1?              -->  1

Jelly,  14 12  11 bytes

Supports (and expects) the character in the input string. Returns \$0\$ or \$1\$.

O*Ɲ%276%7ỊẠ

Try it online!, Truthy test suite, Falsy test suite

How?

Given two consecutive characters of ASCII codes \$x\$ and \$y\$, we want a function that checks whether they form a valid transition.

We need a non-commutative operation, because the result may change when the characters are reversed. For instance, _/ is valid but /_ is not.

Using exponentiation, a possible formula1 is:

$$n=(x^y \bmod 276)\bmod 7$$

The transition is valid if \$n\le1\$, or invalid if \$n>1\$.

 chars |    x |    y | (x**y)%276 | %7 | valid
-------+------+------+------------+----+-------
   __  |   95 |   95 |      71    |  1 |  yes
   _/  |   95 |   47 |     119    |  0 |  yes
   _‾  |   95 | 8254 |     265    |  6 |   no
   _\  |   95 |   92 |     265    |  6 |   no
   /_  |   47 |   95 |      47    |  5 |   no
   //  |   47 |   47 |      47    |  5 |   no
   /‾  |   47 | 8254 |       1    |  1 |  yes
   /\  |   47 |   92 |       1    |  1 |  yes
   ‾_  | 8254 |   95 |     136    |  3 |   no
   ‾/  | 8254 |   47 |      88    |  4 |   no
   ‾‾  | 8254 | 8254 |     196    |  0 |  yes
   ‾\  | 8254 |   92 |     196    |  0 |  yes
   \_  |   92 |   95 |      92    |  1 |  yes
   \/  |   92 |   47 |      92    |  1 |  yes
   \‾  |   92 | 8254 |     184    |  2 |   no
   \\  |   92 |   92 |     184    |  2 |   no

1. Found with a brute-force search in Node.js (using BigInts)

Commented

O*Ɲ%276%7ỊẠ   - main link, taking a string          e.g. "\_/"
O             - get ASCII codes                     -->  [92, 95, 47]
 *Ɲ           - exponentiation on all pairs         -->  [92**95, 95**47]
   %276       - modulo 276                          -->  [92, 119]
       %7     - modulo 7                            -->  [1, 0]
         Ị    - ≤1?                                 -->  [1, 1]
          Ạ   - all values equal to 1?              -->  1
\$\endgroup\$
  • 2
    \$\begingroup\$ lookup table method has won many a problem \$\endgroup\$ – qwr Mar 18 at 20:29
  • \$\begingroup\$ 9 bytes: ⁽"O is the same as 9580. \$\endgroup\$ – Erik the Outgolfer Mar 18 at 22:32
  • \$\begingroup\$ @EriktheOutgolfer Thanks. :) Maybe the script provided in this tip should be updated to support this format (when it's relevant). \$\endgroup\$ – Arnauld Mar 18 at 22:49
  • 1
    \$\begingroup\$ @Arnauld Actually, Jonathan Allan has made this. \$\endgroup\$ – Erik the Outgolfer Mar 18 at 22:56
16
\$\begingroup\$

Ruby -n, 30 bytes

p !/[_\\][\\‾]|[\/‾][_\/]/

Try it online!

Reduces all of the string-breaking sequences to two cases using Regex character classes.

\$\endgroup\$
  • 5
    \$\begingroup\$ You can save 4 bytes by using ~ instead of . I'm not sure if it matters for this challenge, since the character count is the same. \$\endgroup\$ – iamnotmaynard Mar 18 at 16:32
  • \$\begingroup\$ Do you need to escape the /s even though they are within square brackets? \$\endgroup\$ – Solomon Ucko Mar 18 at 22:59
14
\$\begingroup\$

JavaScript (ES6), 45 bytes

The naive way.

s=>!/\/\/|\\\\|_~|~_|~\/|_\\|\/_|\\~/.test(s)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ So this is checking all the invalid pairings, making sure they don't exist in the string? Smart. \$\endgroup\$ – Discrete Games Mar 18 at 15:47
  • \$\begingroup\$ @DiscreteGames Yes, exactly. (Except that I forgot 2 of them. Now fixed.) \$\endgroup\$ – Arnauld Mar 18 at 15:50
  • \$\begingroup\$ 35 bytes: s=>!/[~\/][\/_]|[_\\][\\~]/.test(s). It checks if \/ or ~ end in \/ or _. And then, it check if \\ or _ end in \\ or ~. \$\endgroup\$ – Ismael Miguel Mar 21 at 13:02
  • \$\begingroup\$ @IsmaelMiguel This might be posted as a separate answer, but I'd better leave this one unchanged for reference, as it shows the simplest (as in 'least complicated') regular expression solving the problem. \$\endgroup\$ – Arnauld Mar 21 at 13:05
  • \$\begingroup\$ You can post it as an alternative, but not definitive answer. \$\endgroup\$ – Ismael Miguel Mar 21 at 15:28
10
\$\begingroup\$

R, 89 87 81 78 bytes

-2 bytes thanks to @Giuseppe

-6 bytes thanks to @Nick Kennedy

-3 bytes replacing 1:length(y) with seq(a=y), where a is short for along.with

y=utf8ToInt(scan(,''));all(!diff(cumprod(c(1,y>93)*2-1)[seq(a=y)]*(y%%2*2-1)))

uses \ / _ ~. This is probably not as short as a regex based solution, but I fancied doing something a bit different to everyone else.

utf8ToInt('\\/_~')
# [1]  92  47  95 126

The characters less than 93 switch the state from up to down (or vice versa), and as such behave as -1 while the others do nothing and behave as 1, cumprod tracks the state with respect to the start. The even numbers are in an upstate (represented with -1), the odd numbers are in a down state (1). If the string is unbroken the tracked state multiplied with the up/down position, should not change, it will always be the starting condition (-1,or 1)

Try it online

\$\endgroup\$
  • 2
    \$\begingroup\$ this is quite clever, and a unique R way of doing things! I believe you can remove the () around y%%2 to save 2 bytes, since the special operators %(any)% have a rather high precedence. \$\endgroup\$ – Giuseppe Mar 18 at 18:01
  • 3
    \$\begingroup\$ How about tio for 83 bytes? Takes advantage of the implicit coercion to logical by ! \$\endgroup\$ – Nick Kennedy Mar 18 at 19:43
9
\$\begingroup\$

Python, 46 bytes

f=lambda s:s==''or s[:2]in"__/~~\/\_"*f(s[1:])

Try it online!

Confirms that each adjacent pair of characters connects by checking that they appear consecutively in __/~~\/\_. This string can be viewed as a De_Bruijn_sequence on the \$2^3=8\$ triples of high/low positions.

I tried other less humdrum methods to check character pairs, but they were all longer that hardcoding all legal pairs like this .

\$\endgroup\$
8
\$\begingroup\$

C (gcc), 93 bytes

w,o,r;k(char*_){for(r=0;w=*_,o=*++_;)r|=w-126&&w>47?w-95&&w-92?0:o>47&&o-95:o-92&&o<126;_=r;}

Try it online!

\$\endgroup\$
  • 3
    \$\begingroup\$ I appreciate the w,o,r;k. \$\endgroup\$ – Esolanging Fruit Mar 20 at 3:45
6
\$\begingroup\$

Chip -z, 17 bytes

FZ!C~aS
A}^]--^~t

Try it online! (TIO includes -v to make it easier to understand the output.)

Expects the _/~\ set. Returns either \x00 (falsy) or \x01 (truthy).

The strategy for my answer uses the following information:

Symbol  Binary
   _    0101 1111
   /    0010 1111
   ~    0111 1110
   \    0101 1100
          ^   ^ ^
        HGFE DCBA

A: This bit position happens to be 1 when the left side of the symbol is low, and 0 when it is high
F: This bit position happens to be 0 when the right side of the symbol is low, and 1 when it is high
C: This bit position happens to always be 1

Using this information, I simply need to check that the F of each character matches the not A of the next. An xor gate is a convenient way to accomplish this.

The following code does this, but gives output for each pairing (plus an extra 1 at the start) (7 bytes):

FZ!
A}a

We want to halt at the first failure, and also print whether we have halted within the string, or at the null terminator (we also add -z to give us a null terminator). We can use not C to signify where we stopped, and that gives us this program (13 bytes):

FZ!C~a
A}^]~t

But we still have "leading zeroes" (e.g. \_/\ gives 00 00 00 00 01), so this is transformed to the answer given at the top.

\$\endgroup\$
  • \$\begingroup\$ Nice, I'd noticed this pattern but didn't know a good language to exploit it. \$\endgroup\$ – histocrat Mar 18 at 20:22
6
\$\begingroup\$

05AB1E, 29 14 9 bytes

ÇümŽb‘÷ÈP

Port of @Arnauld's Jelly answer, so make sure to upvote him as well!

Input with .

Try it online or verify all test cases.


Original 29 bytes answer:

„_~SD2×s:Çü-т+•6_üê{↕ƵΔвåO_

Input with ~ instead of .

It sounded shorter in my head.. Will try to golf it down from here.

Try it online or verify all test cases.

Explanation:"

„_~S                          # Push the characters ["_","~"]
    D2×                       # Duplicate it, and increase each to size 2: ["__","~~"]
       s:                     # Swap and replace all "__" with "_" and all "~~" with "~"
                              #  in the (implicit) input-string
         Ç                    # Convert the remaining characters to unicode values
          ü-                  # Calculate the difference between each pair
            т+                # Add 100 to each
              •6_üê{↕       # Push compressed integer 1781179816800959
                       ƵΔ     # Push compressed integer 180
                         в    # Convert the larger integer to Base-180 as list: 
                              #  [52,66,69,100,103,131,179]
                          å   # Check for each if it's in the difference-list
                              # (1 if present; 0 if not)
                           O  # Sum the truthy values
                            _ # Check if this sum is exactly 0 (1 if 0; 0 otherwise)
                              # (and output this result implicitly)

See this 05AB1E tip of mine (sections How to comrpess large integers? and How to compress integer lists?) to understand why •6_üê{↕ is 1781179816800959, ƵΔ is 180 and •6_üê{↕ƵΔв is [52,66,69,100,103,131,179].

Additional explanation:

There are 16 (\$2^4\$) possible pairs of characters we have to verify. If we convert each character to its unicode value, and calculate the differences, we would get these differences. Because compressed integer lists in 05AB1E has to have positive integers only, I add 100 to each. The invalid pairs and their corresponding values are then: ["/_", 52]; ["\~", 66], ["_~", 69], ["//", 100], ["\\", 100], ["_\", 103], ["~_", 131], ["~/", 179], which is why I have the compressed integer list in my code containing these values.
Since __ and ~~ will just like // and \\ result in 0 (or 100 after I add 100), I first remove any adjacent duplicates of ~ and _ in the input-string, before calculating and verifying the pair-differences.

\$\endgroup\$
  • 1
    \$\begingroup\$ Now 9 bytes. \$\endgroup\$ – Arnauld Mar 18 at 23:07
  • \$\begingroup\$ @Arnauld Oh nice! \$\endgroup\$ – Kevin Cruijssen Mar 19 at 7:46
  • \$\begingroup\$ That explanation would work as a string. \$\endgroup\$ – connectyourcharger Mar 19 at 23:57
  • \$\begingroup\$ @connectyourcharger What do you mean? \$\endgroup\$ – Kevin Cruijssen Mar 20 at 7:12
6
\$\begingroup\$

Python 3, 79 70 63 bytes

Saved 16 bytes thanks to Arnauld and Jo King, thanks!

p=lambda s:len(s)<2or((ord(s[-2])%13>5)^ord(s[-1])%2)&p(s[:-1])

Try it online!

Python 3, 67 60 bytes with ~ instead of ‾

p=lambda s:len(s)<2or(~(ord(s[-2])//7^ord(s[-1]))&p(s[:-1]))

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice first answer! You can save 6 bytes by removing some white space. (You may want to add a TIO link, BTW.) \$\endgroup\$ – Arnauld Mar 19 at 0:57
  • 1
    \$\begingroup\$ Thank you! I'm enjoying learning all these tricks \$\endgroup\$ – Joachim Worthington Mar 19 at 22:20
4
\$\begingroup\$

Python 3, 126 bytes

lambda s,d={'‾':'\‾','_':'/_','/':'\‾','\\':'/_'}:len(s)<2or all([s[i+1] in d[s[i]]for i in range(len(s)-1)if s[i]in d])
\$\endgroup\$
4
\$\begingroup\$

Haskell, 70 bytes

This variant uses ~ instead of overlines. It takes all eight valid pairs and checks whether the string only contains those:

f(a:b:x)=[a,b]`elem`words"__ _/ /~ ~~ ~\\ \\_ \\/ /\\"&&f(b:x)
f _=1>0

Try it online!

Ungolfed:

validate :: String -> Bool
validate xs = all valid $ zip xs (tail xs)
  where
    valid (a,b) = [a,b] `elem` starts
    starts      = words "__ _/ /~ ~~ ~\\ \\_ \\/ /\\"
\$\endgroup\$
4
\$\begingroup\$

Perl 6, 32 bytes

{!/< \\\ \~ ~/ // _~ ~_ _\ /_>/}

Try it online!

A regex solution that simply checks that the string contains no invalid sequences.

Explanation:

{                              }   # Anonymous code block
  /<                         >/    # Find the longest sequence from
     \\\                           # \\
         \~                        # \‾
            ~/                     # ‾/
               //                  # //
                  _~               # _‾
                     ~_            # ‾_
                        _\         # _\
                           /_      # /_
 !                                 # And logically negate the match
\$\endgroup\$
4
\$\begingroup\$

R, 43 chars, 47 bytes

It's the same regex the other answers use, but adapted for R.

!grepl('[/‾][/_]|[\\\\_][\\\\‾]',scan(,''))

Try it online!

And obligatory xkcd.

\$\endgroup\$
  • 1
    \$\begingroup\$ you can use ~ in place of to get to 43 bytes, 43 chars. \$\endgroup\$ – Giuseppe Mar 18 at 19:50
  • 2
    \$\begingroup\$ True, but it's more fun with the overbar. :) \$\endgroup\$ – CT Hall Mar 18 at 19:57
4
\$\begingroup\$

Forth (gforth), 100 98 bytes

: x = swap '~ = + ;
: f 1 tuck ?do over i + >r i 1- c@ r> c@ dup 92 x swap dup 47 x <> + loop 0> ;

Try it online!

Explanation

Go through the string and determine whether each character starts on the same position (top or bottom) as the one before ends. Subtract 1 from a counter if they don't match. At the end, if the counter has changed, then the string is not a string.

End position is high if char is / (47) or ~ (126). Otherwise it's low

Start Position is high if char is \ (92) or ~ (126). Otherwise it's low

Code Explanation

\ x is basically just extracting some common logic out into a function to save a few bytes
\ it checks if the first number is equal to the second number
\ or the third number is equal to 126   
: x                \ start a new word definition
  = swap           \ check if the first two numbers are equal then swap with the third
  '~ =             \ checks if the third number is equal to 126
  +                \ adds results together (cheaper version of or)
;                  \ end the word definition

: f                \ start a new word definition
  1 tuck           \ set up parameters for a loop (and create a bool/counter)
  ?do              \ start counted loop from 1 to string-length -1, 
                   \ ?do will skip if loop start and end are the same
    over i +       \ copy the string address and add the loop index to get the char address
    >r i           \ place char address on return stack and place a copy back on the stack
    1- c@          \ subtract 1 to get previous char address and grab ascii from memory
    r> c@          \ move char address back from return stack, then grab from memory
    dup 92 x       \ get the "output" position of the prev character
    swap dup 47 x  \ get the input position of the current character
    <> +           \ check if they aren't equal and add the result to the counter
                   \ the counter won't change if they're equal
  loop             \ end the loop
  0>               \ check if counter is less than 1 (any of the "links" was not valid)
;                  \ end word definition
\$\endgroup\$
3
\$\begingroup\$

Python 3, 80 78 bytes

I don't realy do many python code golfs but I thought I could give it a try

  • -2 bytes: realised not(any()) is the same as all(not()) and could move the not into the r-string
def f(x):*l,=map(r'_/\~'.find,x);return 1-any((i^j//2)%2for i,j in zip(l,l[1:]))

Try it online!

Python 3.8 (pre-release), 71 bytes

I wanted to try out the new := expression assignment

lambda x:all((i^j//2)%2for i,j in zip(l:=[*map(r'\~_/'.find,x)],l[1:]))

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly,  13 12  11 bytes

O*Ɲ%⁽wḃ%5ỊẠ

A monadic Link accepting a list of characters, uses the ~ in place of option.

Try it online! Or see a test-suite (...where I've reordered to place the 8 falsey ones at the end)

This formula was found by fiddling around by hand :p (as were those below)

For this one I too all 16 pairs of character's ordinals treated as an exponentiation and looked for a large modulo that will fit into three bytes followed by a one-byte modulo (1,2,3,4,5,6,7,8,9,10,16,256) that partitioned the 16 such that all of the acceptable results were either 1 or 0 ("insignificant") since I know is shorter than <5, in my previous solution, which was looking for all acceptable results being less than all unacceptable ones.

O*Ɲ%⁽wḃ%5ỊẠ - Link: list of characters
O           - ordinals
  Ɲ         - for each pair of neighbours:
 *          -   exponentiate
    ⁽wḃ     - 30982
   %        - modulo (vectorises)
        5   - five
       %    - modulo (vectorises)
         Ị  - insignificant? (abs(x) <=1) (vectorises)
          Ạ - all truthy?

The possible neighbouring characters and their internal evaluations:

(Ɲ)         (O)            (*%⁽wḃ)        (%5)      (Ị)
pair   a,b=ordinals   c=exp(a,b)%30982   d=c%5   abs(d)<=1
__       95,  95         28471             1         1
_/       95,  47         29591             1         1
/~       47, 126         19335             0         1
/\       47,  92          9755             0         1
~~      126, 126         28000             0         1
~\      126,  92         26740             0         1
\_       92,  95          9220             0         1
\/       92,  47         13280             0         1
~_      126,  95          3024             4         0
~/      126,  47         12698             3         0
\~       92, 126         27084             4         0
\\       92,  92         17088             3         0
_~       95, 126         28169             4         0
_\       95,  92          4993             3         0
/_       47,  95         22767             2         0
//       47,  47          7857             2         0

Previous @ 12:

O*Ɲ%⁽?K%⁴<8Ạ

Try it online!


Previous @ 13:

O%7ḅ6$Ɲ%⁵%8ỊẠ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ For some reason, I thought that was testing abs(x)<1 rather than abs(x)≤1. This offers quite a few more opportunities. :) (I'm stuck at 11 bytes as well for now, though.) \$\endgroup\$ – Arnauld Mar 18 at 21:31
  • \$\begingroup\$ I find that comes in handy very often. \$\endgroup\$ – Jonathan Allan Mar 18 at 21:36
3
\$\begingroup\$

perl 5, 26 25 bytes

using ; as delimiter the end delimiter can be removed

$_=!m;[/~][_/]|[\\_][~\\]

TIO

26 bytes

\$\endgroup\$
3
\$\begingroup\$

Excel, 150 bytes

=SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(A1,"_\",),"_‾",),"‾_",),"‾/",),"/_",),"//",),"\‾",),"\\",)=A1

Removes any invalid pairs, then return true if this results in the original string.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 42 bytes

g=tail>>=zip
h=all(`elem`g"__/~~\\/\\_").g

this solution uses ~, and the function to call is h (i.e., h string gives the answer)

The solution uses a function g that given a list, returns all tuples of adjacent values on the list.

Then we use g to generate the list of allowed neighbors (in g"__/~~\\/\\_") and also the list of all neighboring pairs in the input list. Then we check that each neighboring pair is an allowed pair.

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 41 36 bytes

f(char*_){_=!_[1]||*_/32+*++_&f(_);}

Try it online!

-5 eliminated &1 starting off from an idea from Peter Cordes; changed operators (precedence) to remove parentheses


Uses ~. Checks the first and sixth bits of the first two characters' binary representations:

_ 1011111
\ 1011100
/  101111
~ 1111110
   ^    ^

and traverses the string recursively.

(*_ / 32) & 1 is true only for chars that end high, while *_ & 1 is true only for chars that start low. (x&1) ^ (y&1) == (x+y)&1. XOR is add-without-carry, and carry doesn't disturb the lowest bit. The 1 comes from the f(_) return value, if the rest of the string was stringy.

\$\endgroup\$
  • \$\begingroup\$ Right shifting by 5 leaves the 6th bit at the bottom. So you're checking bits 0 and 5, or the first and sixth bits. (This is a really nice trick, BTW, well done. c&32 is true for chars that end high, while c&1 is true only for chars that start low.) \$\endgroup\$ – Peter Cordes Mar 19 at 22:04
  • \$\begingroup\$ I know the rules only require it to work on at least one implementation, but still worth pointing out that *_ ^ *++_ is undefined behaviour: ^ is not a sequence point, so there's no sequenced-before relationship guaranteeing they get different characters. Of course it's also missing a return, so it only works with gcc -O0 where the function body is a statement-expression. \$\endgroup\$ – Peter Cordes Mar 19 at 22:09
  • \$\begingroup\$ Oops, you're right about the bits. Thanks for catching that \$\endgroup\$ – attinat Mar 19 at 22:31
  • 1
    \$\begingroup\$ Doing &1 twice is redundant. (x^y)&1 == (x&1) ^ (y&1). But given C operator precedence where & has higher priority than ^ (unlike arithmetic operators where + and - have the same priority), we'd need to add () 2 bytes to remove &1 2 bytes, because (x&1) ^ y is not equivalent. But maybe using parens opens up opportunities for some other saving. Fortunately not a problem for an x86 machine-code version of this, where the bit manipulation is very compact... \$\endgroup\$ – Peter Cordes Mar 19 at 22:39
  • \$\begingroup\$ Finished my x86 machine code answer, 13 bytes using this algorithm. \$\endgroup\$ – Peter Cordes Mar 20 at 2:29
2
\$\begingroup\$

Bash, 30 bytes

grep -E '//|\\\\|_~|~_|~/|_\\|/_|\\~'

Input is STDIN. Exit code is 1 if valid, 0 if invalid.

\$\endgroup\$
1
\$\begingroup\$

SNOBOL4 (CSNOBOL4), 58 bytes

	INPUT '/_' | '_\' | '\\' | '//' | '~/' | '\~' @OUTPUT
END

Try it online!

Outputs nothing for truthy and a positive integer (indicating the position of the first break in the string) for falsy.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 32 18 bytes

⌊⭆θ∨¬κ⁼№_/ι№\_§θ⊖κ

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

  θ                 Input string
 ⭆                  Map over characters and convert to string
     κ              Current index
    ¬               Logical Not (i.e. is zero)
   ∨                Logical Or
          ι         Current character
       №            Count (i.e. contained in)
        _/          Literal _/ (i.e. begins at bottom)
      ⁼             Equals
               θ    Input string
              §     Indexed by
                 κ  Current index
                ⊖   Decremented (i.e. previous character)
           №        Count (i.e. contained in)
            \_      Literal \_ (i.e. ended at bottom)
⌊                   Minimum (i.e. if all true)
                    Implicitly print
\$\endgroup\$
1
\$\begingroup\$

x86 machine code, 13 bytes.

(Or 11 bytes without handling single-character strings that are trivially stringy.)

Uses the bit-position check from @attinat's C answer

Same machine code works in 16, 32, and 64-bit modes. The source is NASM for 64-bit mode.

nasm -felf64 -l/dev/stdout  listing
    17   addr                  global string_connected
    18           code          string_connected:
    19           bytes         ;;; input: char *RSI, transitions to check=RCX
    20                         ;;; output: AL=non-zero => connected.  AL=zero disconnected
    21                         .loop:                      ; do {
    22 00000000 AC                 lodsb                   ;   al = *p++
    23 00000001 E309               jrcxz  .early_exit        ; transitions=0 special case.  Checking before the loop would require extra code to set AL.
    24 00000003 C0E805             shr    al, 5
    25 00000006 3206               xor    al, [rsi]          ; compare with next char
    26 00000008 2401               and    al, 1
    27 0000000A E0F4               loopne .loop            ; }while(--rcx && al&1);
    28                         .early_exit:
    29 0000000C C3                 ret

Callable from C as unsigned char string_connected(int dummy_rdi, const char *s, int dummy_rdx, size_t transitions); with the x86-64 System V calling convention. Not bool because the transitions=0 case returns an ASCII code, not 1.

RCX = len = strlen(s) - 1. i.e. the number of character-boundaries = transitions to check in the explicit-length string.

For transitions > 0, returns 0 (mismatch) or 1 (connected) and leaves ZF set accordingly. For transitions == 0, returns the single byte of the string (which is non-zero and thus also truthy). If not for that special case, we could drop the early-exit JRCXZ. It's inside the loop only because AL is non-zero there.


The bit-position logic is based on the observation that bit 0 of the ASCII code tells you the starting height, and bit 5 tells you the ending height.

;;;  _ 1011111
;;;  \ 1011100
;;;  /  101111
;;;  ~ 1111110
;;;     ^    ^

    ; end condition (c>>5) & 1 =>  0 = low
    ; start cond: c&1 => 0 = high
    ; (prev>>5)&1 == curr&1  means we have a discontinuity
    ; ((prev>>5) ^ curr) & 1 == 0  means we have a discontinuity

Test harness (modified from attinat's TIO link, beware the C sequence-point UB in that C reference function). Try it online!. This function is correct for all 30 cases. (Including the single-character cases where the return value doesn't match: both are truthy with different non-zero values in that case.)

\$\endgroup\$
1
\$\begingroup\$

Excel, 79 bytes

Cell A1 as input

=1---SUMPRODUCT(--ISNUMBER(FIND({"//","/_","\~","\\","~/","~_","_\","_~"},A1)))
\$\endgroup\$
0
\$\begingroup\$

Dart, 94 bytes

f(s)=>!(r'//,\\,~/,_\,~_,_~,/_,\~'.split(',').map((t)=>s.contains(t)).fold(false,(p,e)=>p|e));

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C++, 132 110 bytes

-22 bytes thanks to ASCII-only

int f(char*s){int t[128];t[95]=0;t[47]=1;t[92]=2;t[126]=3;for(;*++s;)if(t[s[-1]]%2^t[*s]/2)return 0;return 1;}

Uses a bitmask to know if the start and end are up or down

\$\endgroup\$
  • \$\begingroup\$ hmm. wouldn't porting the C version be golfier :P \$\endgroup\$ – ASCII-only Mar 19 at 0:17
  • \$\begingroup\$ 114 \$\endgroup\$ – ASCII-only Mar 19 at 0:19
  • \$\begingroup\$ 110 \$\endgroup\$ – ASCII-only Mar 19 at 0:25
0
\$\begingroup\$

Retina, 26 bytes

C`[_\\][\\~]|[~\/][_\/]
^0

Try it online!

Uses ~ rather than , because that made it easier to type.

\$\endgroup\$
0
\$\begingroup\$

Regex, 34 bytes

I couldn't find rules on using Regex as a language. Please let me know if I need to adjust this.

^(‾+|(‾*\\)?(_*\/‾*\\)*_*(\/‾*)?)$

Try it here: https://regex101.com/r/s9kyPm/1/tests

\$\endgroup\$
  • 2
    \$\begingroup\$ That's 34 bytes, not 24, right? \$\endgroup\$ – Sara J Mar 19 at 0:18
  • \$\begingroup\$ Well, really 42 bytes, but you can change to ~ \$\endgroup\$ – Jo King Mar 19 at 5:29
0
\$\begingroup\$

APL+WIN, 58 bytes

m←2 2⊤'_/\~'⍳s←,⎕⋄(1+⍴s)=+/((↑m[0;]),m[1;])=m[0;],¯1↑m[1;]

Prompts for input of string, index origin 0 and uses ~ for upper character

Try it online! Courtesy of Dyalog Classic

\$\endgroup\$

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.