No strings attached!

Question

Intro

There are 3 nails in the wall. You've got a piece of string that is fixed to the picture frame with both ends. To hang the picture, you entangled the string with the nails. But before letting the picture go: Can you predict whether the image is going to fall, just by looking at how the string is wrapped around the nails?

In the first example the picture will not fall. In the second example the picture is going to fall.

Challenge

Given the path of the string around N nails, determine whether the picture is going to fall or not. Return a truthy value if the picture is going to fall, and a falsy value otherwise.

Details

• You can assume that the nails and the picture are arranged in a regular N+1-gon, with the picture at the bottom.
• You can assume that there are no knots in the rope, i.e. the rope can be continuously be uwrapped from one of the two ends.
• Each nail is enumerated clockwise with a letter of the alphabet. You can assume that there are at most 26 nails (A-Z).
• A clockwise wrap around a nail is denoted with the lower case letter, a counter clockwise wrap is denoted with an upper case letter.

The first example from above will be encoded as BcA, the second example is encoded as CAbBac.

For the inclined reader: This problem is equivalent to determining whether an element of the free group - generated by the set of nails - is the identity or not. This means it is sufficient to repeatedly cancel substrings like aA or Aa until you reached a fixed point. If the fixed point is an empty string, this is the neutral element, otherwise it is not.

Examples

Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla

  
Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja

Answer 1

Retina, 21 bytes

+`(.)(?!\1)(?i)\1

^$

Try it online!

Like flawr's solution, this just repeatedly deletes adjacent uppercase/lowercase pairs and then checks whether the result is empty or not.

As for how one matches an uppercase/lowercase pair:

(.)     # Match and capture a letter.
(?!\1)  # Ensure that the next character is not the same, to avoid matching
        # "aa" and "AA".
(?i)    # Turn on case-insensitivity.
\1      # Match the backreference. In .NET, when using case insensitivity,
        # backreferences also get case-insensitive, so this *can* still match
        # iff the cases of the two letters are different.

Answer 2

MATLAB, 76 bytes Octave, 82 79 77 bytes

This might be the first time I've seen where MATLAB is actually shorter than Octave (by an entire byte)!

New answer in MATLAB:

c=input('');k='Aa';while k<1e5,k=k+1;c=strrep(c,65+mod(k,64),'');end;~nnz(c)

Answer in Octave:

c=input('');k='Aa';while k++<1e5,c=strrep(c,['',65+mod(k,64)],'');end;~nnz(c)

Saved three five bytes thanks to flawr. ~nnz(c) is shorter than isempty(c), and 'Aa' is two bytes shorter than [0,32].

Try it the Octave-version online!

---

Explanation:

c=input('') asks the user for input. We define k='Aa' as a character array.

while k++<1e5: While loop where both elements in k are incremented each iteration, Aa, Bb, Cc and so on. The loop will continue until the largest element is 1e5, which should be sufficiently high for most strings. It can be increased to 9e9 without increasing the byte count.

We'll take the strrep function in steps, starting from the middle.

By using mod(k,64) we'll get the following when we reach the end of the alphabet (if we convert k back to characters):

ans = Yy
ans = Zz
ans = [{
ans = \|
ans = ]}
ans = ^~
ans = _
ans = `�
ans = aA
ans = bB

As you can see, there will be some symbols in between, but then it will wrap around and start with the alphabet again, but now with the lower case letters first. This is a very short way to check both Aa and aA.

['',65+mod(k,64)] concatenates the numeric values from the mod-call, with an empty string, converting the numbers to characters.

strrep is used to remove elements from the string c and return it. It will search for all occurrences of k in the string and replace it with an empty string.

After 1e5 iterations we'll either have an empty string or a non-empty string. We check if there are any elements in c using nnz(c). We return not(nnz(c)), thus 1 if it's empty, and 0 if there are characters left in c

Answer 3

Minkolang 0.15, 30 bytes

od4&x,N.I1=$6&d3~c-$~48*=,2&xx

Try it here!

Explanation

od                            Take character from input and duplicate it
  4&                          If top of stack is truthy, jump 4 spaces
    x                         Dump top of stack
     ,                        NOT top of stack
      N.                      Output as number and stop

    I1=                       1 if stack has 1 element, 0 otherwise
       $6&                    If top of stack is truthy, jump 16 spaces (to the beginning)
          d3~c                Duplicate top two items of stack, in reversed order
              -               Subtract
               $~             Absolute value
                 48*          Push 32
                    =,        0 if top two items are equal, 1 otherwise
                      2&xx    If top of stack is truthy, dump two elements from top

Minkolang's toroidal nature is leveraged here to eliminate the need for an outer loop. The general idea here is to check if the top two elements of the stack are 32 units apart (meaning they're an uppercase/lowercase pair), and if they are, pop both of them off. Since this is done "in realtime", so to speak, nesting of pairs is handled properly.

Answer 4

Haskell, 98 97 85 81 bytes

This is just a naive implementation that repeatedly tries to cancel adjecent letters until there is no more change, and then determines the result from that.

Thanks @nimi for -12 bytes and @xnor for another -4 bytes!

o=fromEnum
r(a:b:l)|abs(o a-o b)==32=l|1>0=a:r(b:l)
r x=x
f=null.until((==)=<<r)r

Try it online! or Verify all examples!

Answer 5

Haskell, 62 bytes

a%l|b:t<-l,abs(a-b)==32=t|1>0=a:l
f=null.foldr((%).fromEnum)[]

Try it online

Credit to flawr for the abs and Laikoni for the fromEnum map.

The helper function % takes an already-simplified string l, and prepends the symbol a before simplifying the result. If l starts with the inverse character to a, they cancel. Otherwise, a is simply prepended. Note that no further simplification is needed at this stage.

The main function f prepends and simplifies each character in turn via a foldr. Then, it checks whether the result is empty.

To check whether two characters are opposite cases and so should cancel, see if their ASCII values differ by 32. Each element is processed by fromEnum before being passed to %.

Answer 6

05AB1E, 17 bytes

DvADu‚øDíìvyK}}õQ

Try it online!

Explanation

Dv                 # input number of times do:
  A                # push lowercase alphabet
   Du              # push uppercase alphabet
     ‚ø            # zip the alphabets together (['aA', ..., 'zZ'])
       Díì         # prepend a copy with each element reversed ('Aa' ...)
          v        # for each pair in the resulting list
           yK      # remove it from the accumulated string (starts as input)
             }}    # end loops
               õQ  # check result for equality to empty string

Answer 7

Mathematica, 102 bytes

""==StringDelete[""|##&@@#<>#2&~MapThread~{Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}]~FixedPoint~#&

Unnamed function taking an alphabetic string as input and returning True or False.

The heart of the implementation is creating a function that deletes any cancelling pair, like "Pp" or "gG", from a string. The expression {Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a} produces an ordered pair of lists of characters, the first list being {"a","b",...,"Z"} and the second being {"A","B",...,"z"}. Then #<>#2&~MapThread~ produces a list where the corresponding elements of these two lists have been concatenated, that is, {"aA","bB",...,"Zz"}. The fun expression ""|##&@@ then (through the magic of the argument sequence ##) produces a list of alternatives "" | "aA" | "bB" | ... | "Zz"; finally, StringDelete[...] is a function that deletes any occurrence of any of those alternatives from a string.

It now suffices to repeatedly apply that function to the input string until the result doesn't change, which is accomplished by ~FixedPoint~#, and then test whether the result is the empty string with ""==.

Answer 8

JavaScript (ES6), 73 bytes

f=(s,t=s.replace(/(.)\1+/gi,s=>s.replace(/(.)(?!\1)./,'')))=>s==t?!s:f(t)

Unlike .NET, JavaScript has no way of turning off case sensitivity in the middle of a match, so instead we have to find all substrings of repeated letters case insensitively, and then delete any mismatching pair of adjacent characters, which by this point must be an upper/lowercase pair.

Answer 9

Perl, 28 bytes

1 while s/.(??{$&^' '})//;$_

Explanation:

Perl allows one to include a dynamically generated regular expression inside of a standard regular expression.

The . matches anything.

The (??{ is the start of the generated regex.

The $& variable will contain the entire matched string so far, which in this case is just whatever . matched.

The ^ operator does either numeric xor or string xor, depending on the values of the operands. In this case, it will be string xor.

The ' ' is just a string containing a space, which conveniently has the ascii (or unicode!) value of 32. When a space is xor-ed with a char in the range a-z or A-Z, it will change from upper to lower case or vise versa.

The }) is the end of the generated regex.

1 while s/whatever// will repeatedly search for a pattern and replace it with the empty string.

$_ is the default variable. This variable is what perl does fun and exciting stuff upon when you don't specify another variable. Here I'm using it to return a truthy or falsy value, since a zero length string is false, and a nonzero length string which does not equal "0" is true. I'm also assuming that the input string was originally placed in it.

Try it here

Answer 10

Prolog (SWI), 151 bytes

f(S):-S="";string_code(I,S,X),string_code(J,S,Y),J is I+1,32is abs(X-Y),B is J+1,sub_string(S,0,I,_,T),sub_string(S,B,_,0,U),string_concat(T,U,V),f(V).

Takes a long time to run on the longer false cases because of backtracking.

Try it online!

Ungolfed

f(S):-                       The string S corresponds to a falling picture if:
  S="";                      S is the empty string, or...
  string_code(I,S,X),        X is the character code at some index I
  string_code(J,S,Y),        Y is the character code at some index J
  J is I+1,                  J is I+1
  32 is abs(X-Y),            X and Y differ by 32 (difference between lower/upper case)
  B is J+1,                  ...
  sub_string(S,0,I,_,T),     ...
  sub_string(S,B,_,0,U),     ...
  string_concat(T,U,V),      ...
  f(V).                      The concatenation of the substrings before and after 
                             the letters X and Y corresponds to a falling picture.

Answer 11

JavaScript (Node.js), 55 bytes

x=>Buffer(x).map(c=>c==e[i]?--i:e[++i]=c^32,i=e=[])&&!i

Try it online!

Answer 12

MATL, 20 bytes

t"[]yd|32=fX<tQh(]n~

Try it online! Or verify all test cases (it takes a while).

Explanation

t       % Input string implicitly. Duplicate
"       % Do as many times as input size
  []    %   Push empty array
  y     %   Duplicate current string onto the top
  d|    %   Absolute consecutive differences
  32=   %   Convert to true if 32, false otherwise
  fX<   %   Index of first occurrence of true, or empty of all false
  tQ    %   Duplicate, add 1. This gives the next index, or empty
  h     %   Concatenate. Gives the two consecutive indices of letters
        %   to be removed, or empty
  (     %   Assign an empty array to those positions, i.e. delete them
]       % End
n~      % Number of elements, negate

Answer 13

Python 3, 71 bytes

s=input()
for i in s*len(s):s=s.replace(i+i.swapcase(),'')
print(not s)

Try it online!

Answer 14

Wolfram Language (Mathematica), 58 bytes

(Or@@ToCharacterCode@#//.y_||z_/;Abs[y-z]==32:>1<0)===1<0&

Try it online!

Answer 15

C -m32, 100 + 4 = 104 bytes

n;i,k;j;f(s){for(i=0;~++i;)if(k=i%128,n=(k^32)<<8|k,(j=strstr(s,&n))&&k)memmove(j,j+2,strlen(j+1));}

No TIO link, because it takes a few minutes to execute, as it loops through all 32-bit integers.

It takes a char * (zero-terminated string) which will be modified and points to \0 iff the result is empty.

We construct an string containing an uppercase and a lowercase letter with (k^32)<<8|k. When this int is read as a little-endian char *, the top 2 bytes are the null terminator. If that substring is found, we delete these 2 characters with memmove.

Answer 16

Jelly, 15 bytes

ØẠżŒs¤œṣF¥ƒ$ÐLṆ

Try it online!

Outputs 1 if the picture will fall, and 0 if not

How it works

ØẠżŒs¤œṣF¥ƒ$ÐLṆ - Main link. Takes a string S on the left
           $    - Group the previous 2 links into a monad f(S):
     ¤          -   Group previous links into a nilad, A:
ØẠ              -     Alphabet; "ABC...XYZabc...xyz"
   Œs           -     Swapcase; "abc...xyzABC...XYZ"
  ż             -     Zip; ["Aa", "Bb", ..., "Yy", "Zz", "aA", "bB", ..., "yY", "zZ"]
         ¥      -   Group previous 2 links into a dyad g(S, p), where p is some pair of letters:
      œṣ        -     Split S at this pair
        F       -     Flatten
          ƒ     -   Reduce the nilad A by g(S, p), initialising with S on the left
            ÐL  - Repeatedly apply f(S) until a fixed point (empty list if fall, non-empty if not)
              Ṇ - Logical NOT

Answer 17

Cubical Agda 2.6.5, 591 Bytes

Cubical Agda library version a0b4ba3. I use the HEAD version for my convenience, but a standard release version should do. In fact a recent change sort of made the code longer with import reshuffling.

Ungolfed explanation

Let's say Peg is the type of peg numberings. For example, we can just use natural numbers. But letters will work the same.

Peg = ℕ

Why use a string to unfaithfully represent the rope, when you can do better? Let us introduce a new type as a data, similar to Haskell...

data B : Type where
  base : B
  peg : Pegs → base ≡ base

We have a base that represent the base painting, and for each peg, we can "go around it", hence we have an equation base ≡ base. Abstractly, this looks like a bouquet of circles. We can concatenate equations (known as transitivity of equality), or reverse it. As an example:

example : base ≡ base
example = peg 3 ∙ peg 5 ∙ sym (peg 3) ∙ peg 2 ∙ sym (peg 2)

This means "go around peg 3 clockwise, then peg 5, then peg 3 counter-clockwise, etc".

This is clever and all, but how do we use such a type? It turns out dependent types on these things have very janky behavior. For example, we can define a dependent type code : B → Type such that code base is the set of normal forms, and along the path peg a : base ≡ base, we send each normal form b to a * b. This is possible because multiplication on a group gives a bijection of normal forms, so univalence allows an equality code base ≡ code base. Notice how nontrivial computation is performed on an equality of types!

code : B → Type
code base = Σ _ IsNormalised
code (peg a i) = ua (η·≃ (true , a)) i

To set the computation in motion, simply feed it with an equality:

go : ∀ {x} → base ≡ x → code x
go p = subst code p (_ , lower)

These underscores are automatically filled by Agda because she is smart enough to guess what it is (and I'm too annoyed to write it down). This would produce a list. Let's look at one. Evaluating fst (go example), we will get the following list:

(false , 3) ∷ (true , 5) ∷ (true , 3) ∷ []

which represents the normalized string of pegs, notice how the peg 2 gets correctly canceled. Now we just test whether the string is empty.

Golfed code

{-#OPTIONS --cubical #-}
open import Cubical.Foundations.Prelude
open import Cubical.Foundations.Univalence
open import Cubical.Data.Nat
open import Cubical.Data.Bool
open import Cubical.Data.List
open import Cubical.Algebra.Group.Free
data B : Set where
 🖼️ : B
 📍 : ℕ → 🖼️ ≡ 🖼️
open NormalForm ℕ
open Discrete discreteℕ
➿ : B → Set
➿ 🖼️ = Σ _ IsNormalised
➿(📍 a i)= ua(η·≃(true , a))i
🚀 : ∀{x}→ 🖼️ ≡ x → ➿ x
🚀 p = subst ➿ p(_ , lower)
o : 🖼️ ≡ 🖼️ → Bool
o p with 🚀 p
...| [] , _ = true
...| _ = false

Although this is too short to show it, Agda actually has some pretty sophisticated way to shorten the code, because of the arbitrary infix thing. So every golf in haskell involving infix is now 10x more golfy.