In addition to functional languages, I am a big fan of array languages and of stack languages. UIUA is a language which combines both stack and array paradigms. It is in flux right now, and version 0.9.0 is just being released.

The Perl weekly challenge has a new challenge with two parts every week. Moreover, this week hosts challenge 256, a round number. Let’s solve it in Uiua.

You can explore the solutions in a live Uiua pad. The pad also contain the tests shown in the problem statement. If pressing “Runs” displays nothing, it means that every test executed successfully.

But first be warned, the character set used in Uiua is… somewhat unusual.

Perl weekly challenge 256 - part 1

The challenge description is:

You are given an array of distinct words, @words. Write a script to find the maximum pairs in the given array. The words $words[i] and $words[j] can be a pair one is reverse of the other.

In other words (ah ah), we have to find the number of words whose reverse representation is also present in the array and divide this by 2 (so that each word and its reverse representation is counted only once). From the examples, we can also understand that a word cannot be a reverse of itself (for example, “aa” is not to be counted).

Let’s create a word One containing a possible solution.

One ← /+♭↧⊞<.⇡⧻⟜⊞≍⟜∵⇌

Does it work?

One {"aa" "ab" "cd" "dc" "efx" "ba"}
=> 2

Indeed, “ab” and “ba” form a pair, “cd” and “dc” form another one, “aa” is ignored, and “efx” has no counterpart.

Let’s analyze the One function. In Uiua, execution starts from the right. ⇌ means reverse, and ∵ is the each modifier. So ∵⇌ will apply reverse on each element of the array at the top of the stack.

∵⇌ {"aa" "ab" "cd" "dc" "efx" "ba"}
=> {"aa" "ba" "dc" "cd" "xfe" "ab"}

⟜ is the on modifier, new in Uiua 0.9.0. It preserves the element at the top of the stack by restoring it after it has executed its argument. So ⟜∵⇌ will consume the array at the top of the stack and let two element on the stack: the original array at the top, and the array with reverse words below it.

By calling the ⊞ table modifier on the ≍ match function, a matrix will be built by applying the ≍ function to every pair made of an argument of the first array and an argument of a second array (think of a cartesian product with the ≍ function). ≍ returns 1 if two arrays are equivalent (same shape and same content, or same strings) and 0 otherwise.

In our case, the matrix looks like that:

⊞≍⟜∵⇌ {"aa" "ab" "cd" "dc" "efx" "ba"}
=>
╭─             
╷ 1 0 0 0 0 0  
  0 0 0 0 0 1  
  0 0 0 1 0 0  
  0 0 1 0 0 0  
  0 0 0 0 0 0  
  0 1 0 0 0 0  
              ╯

The first one is at index [0 0] and corresponds to “aa” matching itself when reversed. The second one is at index [1 5]: “ab” matches “ba”. Of course, we also have a 1 at index [5 1], since “ba” matches “ab”.

Our matrix is symetrical. Since we do not want to count every pair twice, we have to keep only one half of the matrix. Also, since we do not want words to match themselves when reversed, such as “aa”, we will exclude the diagonal. Filling a square matrix with 1 under the diagonal and 0 everywhere else is easy by using the ⊞ table modifier on the < lower than operator:

⊞< [0 1 2] [0 1 2]
=>
╭─       
╷ 0 0 0  
  1 0 0  
  1 1 0  
        ╯

We can produce the two [0 1 2] arrays by using the ⇡ range function followed by the . duplicate function:

⊞<.⇡3
=>
╭─       
╷ 0 0 0  
  1 0 0  
  1 1 0  
        ╯

Since we do not know the size of the words list in advance, we will use the ⧻ length function on the words list. We will ensure we still have it by prefixing the ⊞≍ table match by ⟜ on:

⊞<.⇡⧻⟜⊞≍⟜∵⇌ {"aa" "ab" "cd" "dc" "efx" "ba"}
=>
╭─             
╷ 1 0 0 0 0 0  
  0 0 0 0 0 1  
  0 0 0 1 0 0  
  0 0 1 0 0 0  
  0 0 0 0 0 0  
  0 1 0 0 0 0  
              ╯
╭─             
╷ 0 0 0 0 0 0  
  1 0 0 0 0 0  
  1 1 0 0 0 0  
  1 1 1 0 0 0  
  1 1 1 1 0 0  
  1 1 1 1 1 0  
              ╯

Note that the top of the stack is represented… at the bottom. Now, by using the ↧ minimum operator, we can force elements of the first matrix to be kept only if the second matrix contains a one. This will eliminate any entry not located under the diagonal:

↧⊞<.⇡⧻⟜⊞≍⟜∵⇌ {"aa" "ab" "cd" "dc" "efx" "ba"}
=>
╭─             
╷ 0 0 0 0 0 0  
  0 0 0 0 0 0  
  0 0 0 0 0 0  
  0 0 1 0 0 0  
  0 0 0 0 0 0  
  0 1 0 0 0 0  
              ╯

This matrix can be transformed into a flat array using the ♭ deshape function. Then the ones and zeroes can be all added together by using the + add function, prefixed by the / reduce modifier which applies its function argument between the values of the flat array. As a consequence, the resut here is 2, as expected.

Perl weekly challenge 256 - part 2

The second part of the challenge is:

Write a script to merge the given strings by adding in alternative order starting with the first string. If a string is longer than the other then append the remaining at the end.

For example, merging “abc” and “12345” should give “a1b2c345”, while merging “abcde” and “123” would yield “a1b2c3de”.

First attempt

An incorrect solution would be

Two ← ▽≠@\0.♭⍉⬚@\0⊟

and appears to work:

Two "abc" "12345"
=> "a1b2c345"

This solution works by putting both strings in an array by using the ⊟ couple function, modified by ⬚@\0 set fill character to NUL. It means that strings will be completed by NUL characters (@\0 in Uiua) so that they have the same length, in order to put them in one array:

⬚@\0⊟ "abc" "12345"
=>
╭─           
╷ "abc\0\0"  
   "12345"   
            ╯

We can then ⍉ transpose this array

⍉⬚@\0⊟ "abc" "12345"
=>
╭─       
╷ "a1"   
  "b2"   
  "c3"   
  "\04"  
  "\05"  
        ╯

then ♭ deshape it as a flat array

♭⍉⬚@\0⊟ "abc" "12345"
=> "a1b2c3\04\05"

NUL characters @\0 can be reverse-identified ≠ in a copy . of the array

≠@\0.♭⍉⬚@\0⊟ "abc" "12345"
=>
"a1b2c3\04\05"
[1 1 1 1 1 1 0 1 0 1]

Using ▽ keep only keep the non-NUL, identified by a 1:

▽≠@\0.♭⍉⬚@\0⊟ "abc" "12345"
=> "a1b2c345"

However, this solution is incorrect: nothing in the problem statement indicates that NUL cannot be contained in the input strings. Since we have no reserved character, we cannot use this technique without risking having a bug.

Second attempt

A longer but correct solution is:

Two ← ⊂⊂♭⍉⊟⊃(↙|↙⊙◌|↘|↘⊙◌)↧∩⧻,,

It seems to work:

Two "abc" "12345"
=> "a1b2c345"

The , over function copies the second element from the top of the stack to the top. Using ,, over over duplicates the two top elements.

The ∩ both modifier applied to ⧻ length replaces the top two elements of the stack by their respective lengths, whose minimum is computed by ↧ minimum:

↧∩⧻,, "abc" "12345"
=>
"12345"
"abc"
3

(don’t forget that the top of the stack is shown at the bottom)

We will now use the ⊃ fork modifier to call four functions with the same view of the stack. All used arguments will be removed from the stack, and the results will be pushed from right to left:

• ↘⊙◌ means ↘ drop followed by dip pop: dip pop is a planet manipulation, which retains the first and third argument on the stack, on which we apply drop to remove some elements from an array. In other words, if the stack contains 3 "abc" "12345" (3 being at the top of the stack), we replace if with "45" which is "12345" with 3 elements dropped.
• ↘ drop with the same 3 "abc" stack (it only uses two elements) returns "", since "abc" only has 3 elements
• ↙ take is the oposite of ↘ drop and keeps the first elements in an array. ↙⊙◌ 3 "abc" "12345" will return “123”
• ↙ 3 "abc" will return "abc"

Using those four functions with the ⊃ fork modifier yields:

⊃(↙|↙⊙◌|↘|↘⊙◌) 3 "abc" "12345"
=>
"45"
""
"123"
"abc"

On the stack, starting from the top, we know have two strings with identical length that we must mix, "abc" and "123", followed by two strings, one being empty, that must be concatenated to the mixed string to get the result.

Note that since the length we use is the minimum of the two strings length, we know that:

• ↙ take and ↘ drop will always succeed since the given index never exceeds the string length.
• The two calls to ↙ take will return strings of the same length, which can be easily put together in a matrix without requiring a fill character to make the lengths match since they are equal.
• At least one of the string returned by ↘ drop will be empty.

By combining and mixing our two strings as we did in the first attempt using ♭⍉⊟ deshape transpose couple, that is couple then transpose then deshape, we just have to use ⊂ join twice to combine all three strings:

⊂⊂♭⍉⊟ "abc" "123" "" "45"
=> "a1b2c345"

and that’s it. Now, our strings can contain all possible unicode characters and our solution will work.

blog comments powered by Disqus