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