D,k,@@*,BF€=B]ßEB*MVcGA$p
D,w,@@,BF€=s1<
D,l,@~,$
L~,AÞwB]dVbUG€k»lbU
Try it online!
How it works
Oddly enough, despite Add++ having a deduplicate command, this doesn't use it. This exits with an error code of 1 when there is no duplicated element.
We start by removing any elements without more than one occurrence, in order to leave the stack with an array containing the original array, preserving order, without any elements which only occur once. This is done by the use of filtering by the dyadic function w:
D,w,@@,BF€=s1<
L~,AÞw
Here, the lambda is implicitly called with the argument. The ~
tells it to unpack its argument to the stack beforehand, then the A
pushes the argument to the stack. Thesefore, if the input looks like [a b c a c]
, the stack would look like
[a b c a c [a b c a c]]
We want this structure, called dyad-binding, due to the way the filter-keep quick, Þ
, works in regard to non-monadic arguments. Here, its functional argument is w, a dyadic (two argument) function. This means that, instead of filtering over each element in the stack using w, it pops the top element of the stack, the list [a b c a c]
in this case, and uses that as the right argument when filtering every other element.
So, for one iteration of w, the stack may look like this at the start of execution:
[[a b c a c] a]
Then BF
flattens the stack, and then we come to another dyadic quick: €
. Again, the popping behaviour is simulated, and a
is used as the left argument to the succeeding function, the equality operator in this case. This compares a
with the elements of [a b c a c]
, yielding an array of 1s and 0s. By now, the stack looks something like this
[1 0 0 1 0]
Finally, s
takes the sum, and 1<
asserts that it is greater than 1. This essentailly counts the occurences of each element of the input in the input itself, and removes them if the count is only 1 i.e. the element isn't duplicated at some point.
After applying Þw
to the input, the stack results in
[a c a c]
We'll call this array A. The rest of the code is determining which of these remaining elements occurs for the second time first i.e. the actual task in the challenge.
Next, we want to perform k over the remaining list. In order to do this, with k being dyadic and taking A as its left argument. Again, we want to create the dyad-binding structure, but using the elements of A instead of the arguments. In a general case, if the stack looks like [a b c d e]
, where a - e
are arbitrary pieces of data, the following code will convert that into a dyad-binding structure:
B]dVbUG
So, this makes our stack look like [a c a c [a c a c]]
, before calling k over €
ach of the elements, using the array as the left argument.
D,k,@@*,BF€=B]ßEB*MVcGA$p
k is our main function to isolate the first deduplicated element. Here, we have our two arguments, I, the element in the array being iterated over, and A, our array containing the elements that occur more than once. The first part of the code, BF€=
, identifies which elements of A are equal to I. Now, we generate the truthy indices - the indices of elements in A that are equal to I. There is a bug in ßE
, causing it to start from 0 (corrected after the challenge was posted). However, as this means the first occurence if I will always be set to 0 because of this bug, and the offset of 1 doesn't change between elements, this means that we can avoid the lengthier dbLBc
which is bug free. Let's use a
as an example value for I. Now, our stack resembles
[[0 1] [1 0] [2 1] [3 0]]
The first element is the 0-based index i, the second whether or not I = A[i]. Next, we remove the indexes where I ≠ A[i], by taking the product of each pair with B*
, then taking the maximum value with MVcG
. Finally, we push I to the stack and pair them as a list. With I as a
, the final value returned is:
[2 a]
This process happens over each element of A, eventually leading to a series of paired lists of the highest index of the element of A in A itself. Finally we want to find the element which has the lowest first element, the element whose duplcicate appears first. Here, as Add++ doesn't have a builtin to get the first or last element of a list, we use our third helper function l:
D,l,@~,$
L~,…»l…
While Add++ doesn't have a builtin for head of an array, it does have a minimum-by quick, »
. We take the list which has the minimum return value when passed through the function l. This helper function unpacks its argument to the stack before performing any commands with the ~
command, then $
swaps them, so the index comes first and is the value returned. Essentially, we return the element with the smallest duplicated element.
Unfortunately, this returns the entire array, both the index and the element, rather than just the element, so we append a bU
to unpack this array to the stack, returning only the last element of the pair - the first duplicated element.
Comments are not for extended discussion; this conversation has been moved to chat.
– Martin Ender – 2017-09-03T13:12:36.197