=========================================
Find Int That Appears Odd Number of Times
=========================================
- Challenge_
.. _Challenge:
https://www.codewars.com/kata/54da5a58ea159efa38000836
.. _int-odd-times-approach-1-search-and-count:
Approach 1 (search and count)
-----------------------------
1. Let *curX* be the first element of the list.
2. Count how many times *curX* appear in the list.
1. If the result is odd, return *curX*.
2. If the result is even or zero.
3. Let *curX* be the next element of the list.
3. Repeat steps 2 to 4, getting the next element of the
list each time (elem 3, elem 4, etc.).
4. If reach the end of the list without getting an odd
count, then return false.
.. _int-odd-times-approach-2-bitwise-xor:
Approach 2 Bitwise XOR
----------------------
.. note::
This approach only works, and works precisely because we are told
there is always one — and always a single one — integer that appears
an odd number of times. They state that:
"There will always be only one integer that appears an odd number
of times."
It is implied by that sentence **and by the example test cases**
that there is never more than one integer that appears an odd
number of times.
XORing :math:`x` to itself an even number of times always yields
:math:`0`.
.. code-block:: text
1 ^ 1 = 0
1 ^ 1 ^ 1 ^ 1 = 0
XORing :math:`x` to :math:`0` yields :math:`x`.
.. code-block:: text
1 ^ 0 = 1
5 ^ 0 = 5
If we XOR :math:`x` an even number of times, the result is always
:math:`0`. It means an even number of :math:`x`'s cancel themselves.
For this challenge, since it is ASSUMED that there will be only one
number that appears an even number of times (and there will always be
one), we can use this bitwise XOR technique to obtain the answer.
.. code-block:: text
1 ^ 1 ^ 3 = 3
1 ^ 2 ^ 1 ^ 2 ^ 3 = 3
The XOR operator has the associative and commutative properties. Thus,
the order of the numbers in the array doesn't matter for this case.
https://en.wikipedia.org/wiki/Exclusive_or#Properties
TypeScript
----------
The original function in Codewars has a return type of simply
`number`. I changed this to `undefined | number` to satisfy `find`
even though the exercise says we can assume there will always be
single number that appears an odd number of times.
Unit Tests
~~~~~~~~~~
The unit tests should work for all approaches and solutions. Changing
the implementation should not produce different results.
.. literalinclude:: /../src/codewars/typescript/6kyu/int-odd-times/find-n.test.ts
:language: typescript
Solution 1 (single function, approach 1)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Using :ref:`approach 1`,
one single function that takes care of the entire logic. Not bad.
.. literalinclude:: /../src/codewars/typescript/6kyu/int-odd-times/find-n-v1.ts
:language: typescript
Solution 2 (helper functions, approach 1)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Also using :ref:`approach
1`, we have the main
``findN`` function which in turn makes use of specialized helper
functions. Looks overkill for this case but the helper functions could
be useful and used in other contexts as well, though. Therefore it is
worth the example.
.. literalinclude:: /../src/codewars/typescript/6kyu/int-odd-times/find-n-v2.ts
:language: typescript
Solution 3 (bitwise XOR)
~~~~~~~~~~~~~~~~~~~~~~~~
The clever solution with :ref:`approach
2` using bitwise
XOR! I did not come up with this solution myself, but instead saw it
from other people's solution. What I did was to write an explanation
on how it works.
.. literalinclude:: /../src/codewars/typescript/6kyu/int-odd-times/find-n-v3.ts
:language: typescript
Scheme
------
The Test Suit
~~~~~~~~~~~~~
.. literalinclude:: /../src/codewars/scheme/6kyu/int-odd-times/find-n.spec.scm
:language: scheme
v1 single function
~~~~~~~~~~~~~~~~~~
.. literalinclude:: /../src/codewars/scheme/6kyu/int-odd-times/find-n-v1.scm
:language: scheme
v2 smaller, composable functions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unit Tests for the Helper Functions
...................................
.. literalinclude:: /../src/codewars/scheme/6kyu/int-odd-times/find-n-v2-helpers.spec.scm
:language: scheme
Implementation using the composed functions
...........................................
.. literalinclude:: /../src/codewars/scheme/6kyu/int-odd-times/find-n-v2.scm
:language: scheme
In this case, we have a *curried* ``eqx?`` function that we partially
apply inside ``oddx?`` to help filter out and then count the number of
times the current ``x`` appear in the list.
v3 car cdr
~~~~~~~~~~
This implementation is a courtesy of `Mario Domenech Goulart`_. It
does not use ``find`` and ``filter`` and instead makes use of ``car``,
``cdr`` and ``null?``. It does not need any help of external libraries
or SRFIs. It is probably the most idiomatic example in terms of
techniques used, like the *loop pattern*, for instance.
.. _`Mario Domenech Goulart`:
http://parenteses.org/mario/
Unit Tests for the Helper Functions
...................................
.. literalinclude:: /../src/codewars/scheme/6kyu/int-odd-times/find-n-v3-helpers.spec.scm
:language: scheme
Implementation using car, cdr and null?
.......................................
.. literalinclude:: /../src/codewars/scheme/6kyu/int-odd-times/find-n-v3.scm
:language: scheme