Jose Angel Munoz

Posted on

# The Urinal Algorithm. How I improved my Python and Go skills with this funny Algorithm

The first time I read about the Urinal Algorithm was in a Reddit post. In fact, the author called it the Men Restroom Algorithm so I named my Urinal Based Algorithm as MenRestRoom. I started to develop my own algorithm based on that post and although it is unfinished, I use it to improve my programming skills.

At the time of writing this article, I realized that the Algorithm with its original name, had some post in StackOverflow even with an Unisex implementation with Priority. It also has a cool document from 2010 called the Urinal Problem which I promise I will review in the future to find ideas to improve mine.

## The Algorithm

The concept is simple: It is a well-researched fact that men in a restroom generally prefer to maximize their distance from already occupied stalls, by occupying the middle of the longest sequence of unoccupied places. For example, consider the situation where ten stalls are empty.

The first visitor will occupy a middle position:

🚽 🚽 🚽 🚽 🚶 🚽 🚽 🚽 🚽 🚽 🚪

In my variant, there is a door, so the left side is clearly the farther stalls from the door. Also I have improved it with emojis. Cool, isn't it?.

The next visitor will use the middle or the farther stall from empty area at the left. Always keeping at least one stall empty between visitors.

🚶 🚽 🚽 🚽 🚶 🚽 🚽 🚽 🚽 🚽 🚪

or

🚽 🚽 🚶 🚽 🚶 🚽 🚽 🚽 🚽 🚽 🚪

The initial sequence can be like:

🚽 🚽 🚽 🚽 🚶 🚽 🚽 🚽 🚽 🚽 🚪

🚶 🚽 🚽 🚽 🚶 🚽 🚽 🚽 🚽 🚽 🚪

🚶 🚽 🚶 🚽 🚶 🚽 🚽 🚽 🚽 🚽 🚪

🚶 🚽 🚶 🚽 🚶 🚽 🚽 🚽 🚶 🚽 🚪

🚶 🚽 🚶 🚽 🚶 🚽 🚶 🚽 🚶 🚽 🚪

Once every other stall is occupied, we can randomly use the rest of the stalls until finish:

🚶 🚽 🚶 🚽 🚶 🚽 🚶 🚶 🚶 🚽 🚪

🚶 🚶 🚶 🚽 🚶 🚽 🚶 🚶 🚶 🚽 🚪

🚶 🚶 🚶 🚽 🚶 🚶 🚶 🚶 🚶 🚽 🚪

🚶 🚶 🚶 🚽 🚶 🚶 🚶 🚶 🚶 🚶 🚪

🚶 🚶 🚶 🚶 🚶 🚶 🚶 🚶 🚶 🚶 🚪

Well, this is how the stalls become occupied but in real life visitors use them for a limited time. Also, the time of peeing is different from visitor to visitor. In the other hand, we assume that the time to take a stall is fixed (By default 2 seconds). The code needs to manage both take and leave functionality at the same time.

As said, the code needs to be improved. When some consecutive stalls gets empty, the algorithm continues to use a random value instead of maximizing the distance. I promise I will work on this option in the future.

Note: I will work on adding some code tests for Python too. I have added some interesting ones for the Golang functions.

## Implementation

I'm going to explain What and How I learned implementing this algorithm in Python and how I used it to learn some Golang techniques.

### Variables

Python and Golang have different variable scopes (Local and Global) but the way to define and use them is harder in Golang. Constant and variables types need to be properly defined and due to the fact that it is a statically typed language, their variables cannot be changed at runtime as with Python.

Additionally, Go is not a pure object oriented programming language. The way to manage functions and how to call them, changes significantly if you are used to program in Python.

Let's define our constants and variables:

#### Constants

Description Constant Type
Maximum time a visitor is occupying a stall maxtimepeeing Int
Minimum time a visitor is occupying a stall mintimepeeing Int
Number of stalls stalls Int
Emoji for door emoDoor string
Emoji for empty stall emoEmpty string
Emoji for taken stall emoTaken string
Stall occupancy frequency stallfreq time.Duration

#### Vars

Description Variable Type
Untaken stalls untaken List of integers
Taken stalls taken List of integers
time a visitor is occupying a stall timePeeing time.Duration
Stall occupied on every iteration stall Int
Left side of the stalls left List of integers
Right side of the stalls right List of integers
Shows stall status on Screen stallPrint List of strings

### The code explained

#### Generate a list of integers

First of all, we need to initialize all our variables with the startup values. We need a list of n untaken stalls.

Python:

``````untaken = list(range(0, stalls))
``````

If `stalls = 4`, it creates the list: [1, 2, 3, 4]

Go:

In go, there is no a built-in range function, so we need to create it first:

``````type Range struct {
MinList int
MaxList int
}

// RangeArray ...
// Created this way to use struct with a function inside a module
func (arrayrange Range) RangeArray() []int {

result := make([]int, arrayrange.MaxList-arrayrange.MinList+1)
for Item := range result {
result[Item] = arrayrange.MinList + Item
}

return result
}

untaken = functions.Range{
MinList: 1,
MaxList: stalls,
}.RangeArray()
``````

I created this way to learn about structs and Object Oriented Programming (OOP) within Go.

#### Generate a random number from a given range

Let's go with the `timepeeing` var. This var will be created at init time (Another important topic that we will review later) and reset with a new value when calling the leaveStall function. It contains a random integer between `mintimepeeing` and `maxtimepeeing`.

Python:

``````timepeeing = random.randint(mintimepeeing, maxtimepeeing)
``````

Golang:

To generate a random value between two values in go, use this:

``````rand.Seed(time.Now().UnixNano())
timePeeing = time.Duration(rand.Intn(maxtimepeeing-mintimepeeing+1) + mintimepeeing)
``````

#### Calculate the stall to be taken on every iteration

In the first iteration, the taken stall is the one in the middle of the untaken row. It is calculated with the sum of the integers of the array and divided by its length. The result is rounded to ceil.

Python:

``````new_stall = round(sum(untaken) / len(untaken) + .5)
``````

Golang:

There is no built-in implementation for the sum of the items of a list. I had to implement too.

``````// Array ...
type Array []int

// SumArray ...
// Created this way to use struct with a function inside a module
func (array Array) SumArray() int {
result := 0
for _, numb := range array {
result += numb
}
return result
}

newStall = int(math.Ceil(float64(functions.Array(untaken).SumArray()) / float64(len(untaken))))
``````

And again, I created this way to learn about OOP within Go. Cool, isn't it?

#### The Left and Right arrays with alternative stalls

The idea is divide the stalls in two (Left and Right) given the already occupied newStall. Having this untaken list:

`[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`

If `newStall` is 5 in this scenario, the left list is `[0, 1, 2, 3, 4]` and the right list `[6, 7, 8, 9]`. Integers 4 and 6 are next to `newStall` and must be empty. Following the same rule, we will build a list of potential stalls to be taken:

For the left side:

`[1, 3]`

For the right side:

`[7, 9]`

Let's do it. In Python, is quite easy:

Python:

``````left = untaken[1:new_stall:2]
right = untaken[new_stall + 2::2]
``````

Again, in golang I had to create a new function:

Golang:

``````// SliceArray ...
func SliceArray(array []int, start int) []int {

result := []int{}
for i := start; i < len(array); i += 2 {
result = append(result, array[i])
}
return result
}

if stalls%2 == 0 {
left = functions.SliceArray(untaken[0:newStall-1], 1)
} else {
left = functions.SliceArray(untaken[0:newStall-1], 0)
}
right = functions.SliceArray(untaken[newStall:], 1)
``````

With this function, we need to check if the `stalls` integer is even or odd to create the `left` list from `untaken` list. The start integer changes depending on the length of the list, something I need to improve in future releases.

#### Printing on screen

This is the easier one for the first stage. We need to prepare the empty stalls with the door and show it on screen:

Python:

``````stall_print = list(emo_empty * stalls + emo_door)
``````

Golang:

``````stallPrint = strings.SplitN(strings.Repeat(emoEmpty, stalls)+emoDoor, "", stalls+1)
``````

#### Init Functions and Methods

Before carry on with the main logic, I think it is interesting to refer about the way Python and Golang manage the Init functions.

The `__init__` in Python is one of the main pieces when talking about OOP. This method initializes the object state. It contains the values and instructions executed at the time of the Object Creation.

The `init()` function in Golang are defined in the package block. It contains the values and instructions executed at the time of the Package call although it runs only once even if the package is imported many times.

#### Variable name convention

I think it is also nice to realize that the name convention changes among programming languages. I recommend to search for the different naming conventions for Python and Golang on the Internet.

For instance:

`stall_print` for Python
`stallPrint` for Go

#### The Take Stall logic

As explained in the section, we need to move items between the `untaken` and `taken` lists and vice versa.

When the process starts, it puts the middle of the stalls in the `taken` and paints the new scenario. After that, it checks if the `left` list has elements to use them. Then the `right` list and finally the ones unoccupied.

The code:

Python:

``````        if untaken:
if not taken:
new_stall = new_stall
else:
if left:
new_stall = random.choice(left)
left.remove(new_stall)
elif right:
new_stall = random.choice(right)
right.remove(new_stall)
else:
new_stall = random.choice(untaken)

untaken.remove(new_stall)
taken.append(new_stall)
``````

Golang:

To get the position of the stall, I created the IndexArray function, also take a look to the append built-in function. The documentation of the built-in package describes append.

`func append(s []T, vs ...T) []T`

``````// IndexArray ...
func IndexArray(array []int, item int) int {
for result := range array {
if array[result] == item {
return result
}
}
return -1
}

if len(untaken) > 0 {
if len(taken) == 0 {
stall = newStall
} else {
if len(left) > 0 {
randomIndex := rand.Intn(len(left))
stall = left[randomIndex]
left = append(left[:randomIndex], left[randomIndex+1:]...)
} else if len(right) > 0 {
randomIndex := rand.Intn(len(right))
stall = right[randomIndex]
right = append(right[:randomIndex], right[randomIndex+1:]...)

} else {
randomIndex := rand.Intn(len(untaken))
stall = untaken[randomIndex]
}
}
stallIndex := functions.IndexArray(untaken, stall)
untaken = append(untaken[:stallIndex], untaken[stallIndex+1:]...)
}
taken = append(taken, stall)

``````
##### Create the stall for printing

To print the output on screen, we need to update the `stallPrint` list:

Python:

In Python, we need two steps, one to remove, one to insert.

``````stall_print.pop(taken[-1])
stall_print.insert(taken[-1], emo_taken)
``````

Golang:

In Go can be done just replacing:

``````stallPrint[taken[len(taken)-1]-1] = emoTaken
``````

#### The Leave Stall logic

A visitor can leave the stall, only when it is taken and following the arrive order (For now).

Python:

``````if taken:
old_stall = taken[0]
taken.remove(old_stall)
untaken.append(old_stall)
``````

Golang:

``````oldStall := taken[0]
taken = append(taken[:0], taken[1:]...)
untaken = append(untaken, oldStall)
``````

The `stall_print` does not change, we just need to leave it empty:

Python:

``````stall_print.pop(old_stall)
stall_print.insert(old_stall, emo_empty)
``````

Golang:

``````stallPrint[oldStall-1] = emoEmpty
``````

And the `timepeeing` is recalculated:

Python:

``````timepeeing = random.randint(mintimepeeing, maxtimepeeing)
``````

Golang:

``````rand.Seed(time.Now().UnixNano())
timePeeing = time.Duration(rand.Intn(maxtimepeeing-mintimepeeing+1) + mintimepeeing)
``````

As discussed, in future revisions we can order the `untaken` list and recalculate left and right with a more complex approach. For now, this is fine to learn.

#### The final touch. Timers

Probably the part that took me more time to put in place. To me, it was important to manage both take and leave options independently with specific times. I was thinking in Threading for Python but it changes the way it is managed in Go. Let's do it.

Python:

As simple as using the Threading Module and:

``````threading.Timer(timepeeing, leave_stall).start()
``````

Where `timepeeing` is the time and `leave_stall()` the function.

Golang:

It took me some time to understand tickers but finally I got it working. Once you get it, the logic it quite simple. Note the `Reset` timer option.

``````takeTicker := time.NewTicker(stallFreq * time.Second)
leaveTicker := time.NewTicker(timePeeing * time.Second)

select {
case <-takeTicker.C:
takeStall()
case <-leaveTicker.C:
leaveStall()
leaveTicker.Reset(timePeeing * time.Second)
}
``````

#### Orchestrating the solution

The program starts with the untaken list totally full, so we need to run the solution until the list becomes totally empty:

Python:

After creating the `newpee` object, we check the `untaken` variable:

``````while newpee.untaken:
``````

To print the result:

``````for item in newpee.stall_print:
print(item, end=' ', flush=True)
``````

Golang:

The golang Tour says: For is Go's "while". Then:

``````for len(untaken) > 0 {
}
``````

To print:

``````for _, item := range stallPrint {
fmt.Print(item + " ")
``````

## Final words

I'm sure that the algorithm can be improved in functionality, efficiency and style but the idea is to focus in learning and having a small challenge to learn a new language.

Don't forget to implement good practices and create unit tests for your libraries and functions. This is my first approach for golang just to understand how testing is implemented:

``````package functions

import (
"reflect"
"testing"
)

var mylist = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

func TestRangeArray(t *testing.T) {
expected := mylist
newarray := Range{
MinList: 1,
MaxList: 10,
}
ret := newarray.RangeArray()

if !reflect.DeepEqual(ret, expected) {
t.Errorf("RangeArray() = %q, want %q", ret, expected)
}
}

func TestSumArray(t *testing.T) {
expected := 55
newarray := Array(mylist)
if ret := newarray.SumArray(); ret != expected {
t.Errorf("SumArray() = %q, want %q", ret, expected)
}
}

func TestSliceArray(t *testing.T) {
expectede := []int{2, 4, 6, 8, 10}
rete := SliceArray(mylist, 1)
expectedo := []int{1, 3, 5, 7, 9}
reto := SliceArray(mylist, 0)

if !reflect.DeepEqual(rete, expectede) {
t.Errorf("SliceArray() = %q, want %q", rete, expectede)
}

if !reflect.DeepEqual(reto, expectedo) {
t.Errorf("SliceArray() = %q, want %q", reto, expectedo)
}
}

func TestIndexArray(t *testing.T) {
expected := 5

if ret := IndexArray(mylist, 6); ret != expected {
t.Errorf("SumArray() = %q, want %q", ret, expected)
}
}
``````

You can find the code here and here.

Thanks for reading and keep improving!