| Bytes | Lang | Time | Link |
|---|---|---|---|
| 591 | Cubical Agda 2.6.5 | 240609T172146Z | Trebor |
| 015 | Jelly | 230103T162305Z | caird co |
| 055 | JavaScript Node.js | 180427T075228Z | l4m2 |
| nan | C m32 | 230102T122358Z | corvus_1 |
| 058 | Wolfram Language Mathematica | 170115T065352Z | alephalp |
| 071 | Python 3 | 190913T145743Z | Jitse |
| 028 | Perl | 170114T012911Z | BenGoldb |
| 076 | MATLAB | 170113T173440Z | Stewie G |
| 020 | MATL | 170114T005651Z | Luis Men |
| 073 | JavaScript ES6 | 170114T004418Z | Neil |
| 062 | Haskell | 170113T233730Z | xnor |
| 081 | Haskell | 170113T171224Z | flawr |
| 151 | Prolog SWI | 170113T182609Z | Business |
| 017 | 05AB1E | 170113T175505Z | Emigna |
| 030 | Minkolang 0.15 | 170113T173608Z | El'e |
| 102 | Mathematica | 170113T173806Z | Greg Mar |
| 021 | Retina | 170113T172545Z | Martin E |
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.
Jelly, 15 bytes
ØẠżŒs¤œṣF¥ƒ$ÐLṆ
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
JavaScript (Node.js), 55 bytes
x=>Buffer(x).map(c=>c==e[i]?--i:e[++i]=c^32,i=e=[])&&!i
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.
Wolfram Language (Mathematica), 58 bytes
(Or@@ToCharacterCode@#//.y_||z_/;Abs[y-z]==32:>1<0)===1<0&
Python 3, 71 bytes
s=input()
for i in s*len(s):s=s.replace(i+i.swapcase(),'')
print(not s)
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.
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
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
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.
Haskell, 62 bytes
a%l|b:t<-l,abs(a-b)==32=t|1>0=a:l
f=null.foldr((%).fromEnum)[]
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 %.
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
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.
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.
05AB1E, 17 bytes
DvADu‚øDíìvyK}}õQ
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
Minkolang 0.15, 30 bytes
od4&x,N.I1=$6&d3~c-$~48*=,2&xx
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.
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 ""==.
Retina, 21 bytes
+`(.)(?!\1)(?i)\1
^$
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.