99
\$\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\$
9
  • 38
    \$\begingroup\$ Welcome to PPCG! Nice first challenge. \$\endgroup\$ Commented Mar 18, 2019 at 15:30
  • 1
    \$\begingroup\$ Are the characters specified in your challenge the only ones that will appear in the string? \$\endgroup\$
    – Gymhgy
    Commented Mar 18, 2019 at 15:31
  • \$\begingroup\$ @EmbodimentofIgnorance Yes, only the 4. \$\endgroup\$ Commented Mar 18, 2019 at 15:34
  • 33
    \$\begingroup\$ Wait you could make a language out of this \$\endgroup\$
    – Delioth
    Commented Mar 18, 2019 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\$ Commented Mar 19, 2019 at 4:35

36 Answers 36

39
\$\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\$
4
  • 3
    \$\begingroup\$ lookup table method has won many a problem \$\endgroup\$
    – qwr
    Commented Mar 18, 2019 at 20:29
  • \$\begingroup\$ 9 bytes: ⁽"O is the same as 9580. \$\endgroup\$ Commented Mar 18, 2019 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
    Commented Mar 18, 2019 at 22:49
  • 1
    \$\begingroup\$ @Arnauld Actually, Jonathan Allan has made this. \$\endgroup\$ Commented Mar 18, 2019 at 22:56
17
\$\begingroup\$

Ruby -n, 30 bytes

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

Try it online!

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

\$\endgroup\$
2
  • 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\$ Commented Mar 18, 2019 at 16:32
  • \$\begingroup\$ Do you need to escape the /s even though they are within square brackets? \$\endgroup\$ Commented Mar 18, 2019 at 22:59
14
\$\begingroup\$

JavaScript (ES6), 45 bytes

The naive way.

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

Try it online!

\$\endgroup\$
5
  • 2
    \$\begingroup\$ So this is checking all the invalid pairings, making sure they don't exist in the string? Smart. \$\endgroup\$ Commented Mar 18, 2019 at 15:47
  • \$\begingroup\$ @DiscreteGames Yes, exactly. (Except that I forgot 2 of them. Now fixed.) \$\endgroup\$
    – Arnauld
    Commented Mar 18, 2019 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\$ Commented Mar 21, 2019 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
    Commented Mar 21, 2019 at 13:05
  • \$\begingroup\$ You can post it as an alternative, but not definitive answer. \$\endgroup\$ Commented Mar 21, 2019 at 15:28
11
\$\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\$
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
  • 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
    Commented Mar 18, 2019 at 18:01
  • 3
    \$\begingroup\$ How about tio for 83 bytes? Takes advantage of the implicit coercion to logical by ! \$\endgroup\$ Commented Mar 18, 2019 at 19:43
9
\$\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\$
1
  • 5
    \$\begingroup\$ I appreciate the w,o,r;k. \$\endgroup\$ Commented Mar 20, 2019 at 3:45
7
\$\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\$
4
  • 1
    \$\begingroup\$ Now 9 bytes. \$\endgroup\$
    – Arnauld
    Commented Mar 18, 2019 at 23:07
  • \$\begingroup\$ @Arnauld Oh nice! \$\endgroup\$ Commented Mar 19, 2019 at 7:46
  • \$\begingroup\$ That explanation would work as a string. \$\endgroup\$
    – moltarze
    Commented Mar 19, 2019 at 23:57
  • \$\begingroup\$ @connectyourcharger What do you mean? \$\endgroup\$ Commented Mar 20, 2019 at 7:12
7
\$\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
  • 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
    Commented Mar 19, 2019 at 0:57
  • 1
    \$\begingroup\$ Thank you! I'm enjoying learning all these tricks \$\endgroup\$ Commented Mar 19, 2019 at 22:20
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\$
1
  • \$\begingroup\$ Nice, I'd noticed this pattern but didn't know a good language to exploit it. \$\endgroup\$
    – histocrat
    Commented Mar 18, 2019 at 20:22
5
\$\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\$
2
  • \$\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
    Commented Mar 18, 2019 at 21:31
  • \$\begingroup\$ I find that comes in handy very often. \$\endgroup\$ Commented Mar 18, 2019 at 21:36
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\$

perl 5, 26 25 bytes

using ; as delimiter the end delimiter can be removed

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

TIO

26 bytes

\$\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\$
2
  • 1
    \$\begingroup\$ you can use ~ in place of to get to 43 bytes, 43 chars. \$\endgroup\$
    – Giuseppe
    Commented Mar 18, 2019 at 19:50
  • 3
    \$\begingroup\$ True, but it's more fun with the overbar. :) \$\endgroup\$
    – Chthonyx
    Commented Mar 18, 2019 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\$
4
\$\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\$
4
\$\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\$
5
  • \$\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\$ Commented Mar 19, 2019 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\$ Commented Mar 19, 2019 at 22:09
  • \$\begingroup\$ Oops, you're right about the bits. Thanks for catching that \$\endgroup\$
    – att
    Commented Mar 19, 2019 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\$ Commented Mar 19, 2019 at 22:39
  • \$\begingroup\$ Finished my x86 machine code answer, 13 bytes using this algorithm. \$\endgroup\$ Commented Mar 20, 2019 at 2:29
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\$

Bash, 30 bytes

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

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

\$\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\$
2
\$\begingroup\$

Retina, 24 bytes

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

Try it online!

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

  • -2 bytes by removing some unnecessary backslashes (thanks to @Neil)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I don't think you need the backslashes before the slashes. \$\endgroup\$
    – Neil
    Commented Mar 20, 2020 at 10:56
  • \$\begingroup\$ @Neil Apparently I don't, thanks for pointing it out! \$\endgroup\$
    – Sara J
    Commented Mar 20, 2020 at 13:49
  • 2
    \$\begingroup\$ If you use ~ instead of , shouldn't that also be the case for your input in your TIO? \$\endgroup\$ Commented Mar 20, 2020 at 15:32
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\$

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
  • 2
    \$\begingroup\$ That's 34 bytes, not 24, right? \$\endgroup\$
    – Sara J
    Commented Mar 19, 2019 at 0:18
  • \$\begingroup\$ Well, really 42 bytes, but you can change to ~ \$\endgroup\$
    – Jo King
    Commented Mar 19, 2019 at 5:29
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\$
1
\$\begingroup\$

naz, 142 bytes

2a2x1v4a8m1s2x2v2m2s2x3v3a2x4v3d4m2a2x5v1x1f1r3x2v2e3x3v3e3x4v3e2f0x1x2f1r3x1v4e3x3v3e3x5v2e0m1o0x1x3f1r3x1v4e3x2v2e3x4v3e0m1o0x1x4f0m1a1o0x1f

Another answer with a lot of conditionals - so many, in fact, that halfway through writing the explanation for a 206-byte solution, I realized an optimization I could make to achieve this one.

Works for any input string terminated with the control character STX (U+0002). ~ is expected instead of .

Explanation (with 0x commands removed)

2a2x1v                       # Set variable 1 equal to 2
4a8m1s2x2v                   # Set variable 2 equal to 47 ("/")
2m2s2x3v                     # Set variable 3 equal to 92 ("\")
3a2x4v                       # Set variable 4 equal to 95 ("_")
3d4m2a2x5v                   # Set variable 5 equal to 126 ("~")
1x1f                         # Function 1
    1r                       # Read a byte of input
      3x2v2e                 # Jump to function 2 if it equals variable 2
            3x3v3e3x4v3e     # Jump to function 3 if it equals variable 3 or variable 4
                        2f   # Otherwise, jump to function 2
1x2f                         # Function 2
    1r                       # Read a byte of input
      3x1v4e                 # Jump to function 4 if it equals variable 1
            3x3v3e           # Jump to function 3 if it equals variable 3
                  3x5v2e     # Jump back to the start of the function if it equals variable 5
                        0m1o # Otherwise, output 0
1x3f                         # Function 3
    1r                       # Read a byte of input
      3x1v4e                 # Jump to function 4 if it equals variable 1
            3x2v2e           # Jump to function 2 if it equals variable 2
                  3x4v3e     # Jump back to the start of the function if it equals variable 4
                        0m1o # Otherwise, output 0
1x4f0m1a1o                   # Function 4
                             # Output 1
1f                           # Call function 1
\$\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\$

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 and acknowledge you have read our privacy policy.

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