# Solving english ruler problem using recursion in python and swift

We must print an english ruler using recursion . An english ruler is ruler where each unit has a number of tick. a unit can be divided into smaller units at 1/2 the interval 1/4 the interval 1/8 the interval , for each smaller unit , we must remove one tick .

```# an example of english ruler of length 2
# each unit is formed of 4 ticks
---- 2
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 0```

```# an english ruler with length of three
# each unit is formed of 4 ticks
----- 3
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 2
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 1
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 0```

## The english ruler algorithm

```# in this example we want to generate a ruler
# which has a length of 1 inch
# and where the inch has a five ticks
----- 1
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 0```

we notice that we need to generate this series The first number five represents a full unit , so it represents the zero unit , and the second number five represents a full unit , the 1 inch unit . So we want to generate the units between [0-1]. These units can be represented by using a string . We notice that

• when the string has a length of zero or when it has a length which is odd , we must insert a new number . We start counting from n = zero. So the number that we must insert is n+1 , so it is is 1 , 2 , 3 , 4
• when the string has a length of even , we must concatenate this string with itself minus the last number .
• when the string has a length of (2^(5-1)) -1 , we must stop . So when it has a length of ( 2 to the power the number of ticks -1) -1 , we must stop. ## Implementing an english ruler using python

```def printRuler(inches, numberOfTickPerInch):
'''
print a ruler
@param inches  : number of inches
@param numberOfTickPerInch : number of tick per inche
'''
# if inches == 0  or at inch 0 print the inch and stop
if inches == 0:
printTick(numberOfTickPerInch, inches)
# if inch > 0
if inches > 0:
# start by printing the full inche , so all the number of ticks
printTick(numberOfTickPerInch, inches)
# generate the units contained in each inch that we must print
for numberStr in generateRulerSeries(2**(numberOfTickPerInch - 1) - 1):
# print the ticks in each unit
printTick(int(numberStr))
# recursively recall the printRuler with the next inch to print
printRuler(inches - 1, numberOfTickPerInch)

def printTick(number, unit=-1):
'''
print a -
@param number number of - to print
@param unit full unit if we are at full unit print the number of the unit
if the unit number is -1 don t print the unit number
'''
if number == 0:
if unit != -1:
# at full unit print the number of the unit e.g 1 , 2 , 3
print(f' {unit}', end='')
print()
return
print('-', end='')
# recursively print the next - till the number of ticks is zero
printTick(number - 1, unit)

def generateRulerSeries(stop, series='', n=0, generatedSeries={}):
'''Generate ruler series

@param stop  the length of the serie where we must stop
@param series the series that we will generate start with the empty serie
@param  n  the increment factor
@param generatedSeries  the generated series for each stop  e.g {15: '121312141213121'}
used for caching so we generate the serie only once , if the 15 series is already generated return it
else generate it and store it inside the dictionary
'''

# check if we have already generated the series if so return it
if generatedSeries.get(stop) is not None:
return generatedSeries[stop]

if len(series) == stop:
generatedSeries[stop] = series
# if the serie has a length of stop stop ad return the generated serie
return series
if len(series) % 2 == 1 or len(series) == 0:
# if the length of the serie is 0 or is odd add the next n
return generateRulerSeries(stop, f'{series}{n+1}', n+1)
else:
# if the lenth of the serie is even concatenate this serie with itself minus the last element
return generateRulerSeries(stop, f'{series}{series[0:len(series)-1]}', n)
```

```printRuler(3, 4)

---- 3
-
--
-
---
-
--
-
---- 2
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 0```

```printRuler(2, 2)

-- 2
-
-- 1
-
-- 0```

## Implementing an english ruler using swift

```import Darwin

/*
@param _ stop : Int  the length of the serie where we must stop
@param _ series : String the series that we will generate start with the empty serie
@param  _ n : Int  the increment factor
@return String
@perform generate a ruler serie
*/

func generateRulerSeries(_ stop : Int, _ series : String = "", _ n: Int = 0) -> String{

if series.count == stop{
//if the serie has a length of stop stop ad return the generated serie
return series
}
if series.count % 2 == 1 || series.count == 0{
//if the length of the serie is 0 or is odd add the next n
return generateRulerSeries(stop, "\(series)\(n+1)", n+1)
}
else{
//if the lenth of the serie is even concatenate this serie with itself minus the last element
return generateRulerSeries(stop, "\(series)\(series[series.startIndex ..< series.index(series.endIndex , offsetBy: -1)])", n)
}

}

/*

@param  _ number : Int  number of - to print
@param  _ unit:Int  if we are at full unit print the number of the unit
if -1 don't print the full unit

@perform print a -
*/
func printTick(_ number : Int , _ unit : Int = -1){
if number == 0{
if unit != -1{
//at full unit print the number of the unit e.g 1 , 2 , 3
print(" \(unit)" , separator :"" , terminator : "")
}
print()
return
}
print("-", separator :"" , terminator : "")
//recursively print the next - till the number of ticks is zero
printTick(number - 1, unit)

}

/*
@param _ inches :Int   number of inches
@param _ numberOfTickPerInch : Int  number of tick per inches
@performs : print a ruler
*/
func printRuler( _ inches : Int, _ numberOfTickPerInch : Int ){
//if inches == 0  or at inch 0 print the inch and stop
if inches == 0{
printTick(numberOfTickPerInch, inches)
}
//if inch > 0
if inches > 0{
//start by printing the full inche , so all the number of ticks
printTick(numberOfTickPerInch, inches)
//generate the units contained in each inch that we must print

for numberStr in generateRulerSeries(Int(pow(2.0 , Double(numberOfTickPerInch - 1)) ) - 1 ){
//print the ticks in each unit
printTick(Int(String(numberStr))!)
}
//recursively recall the printRuler with the next inch to print
printRuler(inches - 1, numberOfTickPerInch)
}
}

```

```#printRuler(2, 4)
---- 2
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 0```