# Write Python programs by means of Emacs' toolbox

## Table of Contents

- #1 Vowels counter
- #2 Last digit of a large number
- #3 How many times does it contain?
- #4 Second Variation on Caesar Cipher
- #5 Did I Finish my Sudoku?
- TODO #6 Vigenère Autokey Cipher Helper
- DONE #7 Human readable duration format
- TODO #8 Battleship field validator
- TODO #9 Instant Runoff Voting
- DONE #10 Base64 Numeric Translator
- TODO #11 Elementary Arithmetic - Carries Count
- DONE #12 Valid Parentheses
- DONE #13 Coordinates Validator
- TODO #14 Pete, the baker
- DONE #15 Decode the Morse code
- TODO #16 Next bigger number with the same digits
- DONE #17 Simple fraction to mixed number converter
- TODO #18 Common denominator
- DONE #19 Strip Url Params
- DONE #20 Strip Comments
- DONE #21 RGB To Hex Conversion
- DONE #22 Calculator
- TODO #23 Twice linear
- TODO #24 Molecule to atoms
- TODO #25 Next bigger number with the same digits
- DONE #26 Catching Car Mileage Numbers
- TODO #27 Finding an appointment
- DONE #28 Scramblies
- TODO #29 IP Validation
- TODO #30 Matrix operations
- #31 Longest common subsequence
- #32 Design a Simple Automaton (Finite State Machine)
- #33 Pick peacks
- #34 Permutations
- #35 Palindrome generator
- #36 The observed PIN

## #1 Vowels counter

### Description

Return the number (count) of vowels in the given string. We will consider a, e, i, o, and u as vowels for this Kata.

### Solution

def getCount(inputStr): num_vowels = 0 # your code here for letter in inputStr: list_of_vowels = ['a', 'e', 'i', 'o', 'u'] if letter in list_of_vowels: num_vowels += 1 #print(letter) #print(num_vowels) return num_vowels input_string = 'John the dully boy write this book' print(getCount(input_string)) assert(getCount(input_string) == 9)

9

## #2 Last digit of a large number

### Description

Define a function

def last_digit(n1, n2): return

that takes in two numbers a and b and returns the last decimal digit of a^b. Note that a and b may be very large!

For example, the last decimal digit of 9

^{7}is 9, since 9^{7}= 4782969. The last decimal digit of (2^{200})^{(2300)}, which has over 10^{92}decimal digits, is 6.The inputs to your function will always be non-negative integers. Examples

last_digit(4, 1) # returns 4 last_digit(4, 2) # returns 6 last_digit(9, 7) # returns 9 last_digit(10, 10

* 10) # returns 0 last_digit(2 *200, 2 ** 300) # returns 6Remarks JavaScript

Since JavaScript doesn't have native arbitrary large integers, your arguments are going to be strings representing non-negative integers, e.g.

lastDigit("10", "10000000000");

The kata is still as hard as the variants for Haskell or Python, don't worry.

### Code

#### Visualise the matrix of number's orders

def simple_array(): l = [] for i in range(10): l.append([i] + [str(i**j)[-1] for j in range(10)]) return l for i in simple_array(): print(i)

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

#### Seeking for the sequences

- Static are 0, 1, 5, 6
- 0 as an order determiner has deviation from general rule

- Periodic are 2, 3, 4, 7, 8, 9
- 2: [2, 4, 6, 8]
- 3: [3, 9, 7, 1]
- 4: [4, 6, 4]
- 7: [7, 9, 3, 1]
- 8: [8, 4, 2, 6]
- 9: [9, 1]

#### Entire meta-data

For simplification purposes lets create a full set of rules.

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

#### Predict sequence

def seq0(num): return 0 def seq1(num): return 1 def seq2(num): if num > 0: s = [2, 4, 8, 6] if num < 5: return s[num-1] else: return s[num % 4 - 1] else: return 1 assert(seq1(22) == 1) assert(seq0(100) == 0) assert(seq2(2) == 4) assert(seq2(4) == 6) assert(seq2(5) == 2) assert(seq2(10) == 4) print('Tests passed')

Tests passed

#### Function generator

def first(n): return n + 1 def second(n): return n + 2 def function_generator(k, n): list_of_functions = [first(n), second(n)] return list_of_functions[k] print(function_generator(0, 10))

11

#### Ties these snippets together

def seq0(num): return 0 def seq1(num): return 1 def seq2(num): if num > 0: s = [2, 4, 8, 6] if num < 5: return s[num-1] else: return s[num % 4 - 1] else: return 1 def func_gen(k, n): list_of_functions = [seq0(n), seq1(n), seq2(n)] return list_of_functions[k] assert(func_gen(2, 10) == 4) print('It works!')

It works!

#### Further development

Obvious that `seqN()`

for other numbers should be similar.
Following *DRY* principle lets take an attempt to cope with it
and …

#### Function itself

def seq0(num): return 0 def seq1(num): return 1 def seq2(num): if num > 0: s = [2, 4, 8, 6] if num < 5: return s[num-1] else: return s[num % 4 - 1] else: return 1 def last_digit(k, n): list_of_functions = [seq0(n), seq1(n), seq2(n)] return list_of_functions[k] assert(last_digit(2, 10) == 4) print('It works!') assert(last_digit(2, 11) == 8) assert(last_digit(1, 10) == 1) print('It works! also')

It works! It works! also

#### Final version

Seems like all `seqN`

functions might be elegantly
fit into the one.

def last_digit(num, order): if num > 9: num = int(str(num)[-1]) if order > 0: s = [[0, 0], [1, 1], [2, 4, 8, 6], [3, 9, 7, 1], [4, 6], [5, 5], [6, 6], [7, 9, 3, 1], [8, 4, 2, 6], [9, 1]][num] if order < len(s) + 1: return s[order-1] else: return s[order % len(s) - 1] else: return 1 assert(last_digit(2, 10) == 4) assert(last_digit(12, 10) == 4) assert(last_digit(22, 11) == 8) assert(last_digit(7, 2) == 9) assert(last_digit(27, 2) == 9) assert(last_digit(2 ** 200, 2 ** 300) == 6)

#### Clever solution

def last_digit(n1, n2): return pow( n1, n2, 10 ) assert(last_digit(2 ** 200, 2 ** 300) == 6)

## #3 How many times does it contain?

### Description

Your task is to return how many times a string contains a given character.

The function takes a string(inputS) as a paremeter and a char(charS) which is the character that you will have to find and count.

For example, if you get an input string "Hello world" and the character to find is "o", return 2.

### Code

def string_counter(string, char): return string.count(char) assert(string_counter('Hello World', 'o') == 2)

## #4 Second Variation on Caesar Cipher

### Description

Description:

In this country soldiers are poor but they need a certain level of secrecy for their communications so, though they do not know Caesar cypher, they reinvent it in the following way.

They use ASCII, without really knowing it, but code only letters a-z and A-Z. Other caracters are kept such as.

They change the "rotate" each new message. This "rotate" is a prefix for their message once the message is coded. The prefix is built of 2 letters, the second one being shifted from the first one by the "rotate", the first one is the first letter, after being downcased, of the uncoded message.

For example if the "rotate" is 2, if the first letter of the uncoded message is 'J' the prefix should be 'jl'.

To lessen risk they cut the coded message and the prefix in five pieces since they have only five runners and each runner has only one piece.

If possible the message will be evenly split between the five runners; if not possible, parts 1, 2, 3, 4 will be longer and part 5 shorter. The fifth part can have length equal to the other ones or shorter. If there are many options of how to split, choose the option where the fifth part has the longest length, provided that the previous conditions are fulfilled. If the last part is the empty string don't put this empty string in the resulting array.

For example, if the coded message has a length of 17 the five parts will have lengths of 4, 4, 4, 4, 1. The parts 1, 2, 3, 4 are evenly split and the last part of length 1 is shorter. If the length is 16 the parts will be of lengths 4, 4, 4, 4, 0. Parts 1, 2, 3, 4 are evenly split and the fifth runner will stay at home since his part is the empty string and is not kept.

Could you ease them in programming their coding?

Example with shift = 1 :

message : "I should have known that you would have a perfect answer for me!!!"

code : => ["ijJ tipvme ibw", "f lopxo uibu z", "pv xpvme ibwf ", "b qfsgfdu botx", "fs gps nf!!!"]

By the way, maybe could you give them a hand to decode?

### Solution

#### Appropriate view and test suite

def encode_str(strng, shift): # your code pass def decode(arr): #your code pass u = "I should have known that you would have a perfect answer for me!!!" v = ["ijJ tipvme ibw", "f lopxo uibu z", "pv xpvme ibwf ", "b qfsgfdu botx", "fs gps nf!!!"] assert(encode_str(u, 1) == v) u = "O CAPTAIN! my Captain! our fearful trip is done;" v = ["opP DBQUBJ", "O! nz Dbqu", "bjo! pvs g", "fbsgvm usj", "q jt epof;"] assert(encode_str(u, 1) == v)

#### Task set dissection

- Shift value determiner;
- Cyclic shift for letters;
- Cyclic shift for capital letters;
- Entire message split technique.

#### Gauge the shift value

def gauge_shift(first_message): return ord(first_message[1]) - ord(first_message[0]) assert(gauge_shift("jk Jack") == 1)

#### Shift letter task

letters = [chr(i) for i in range(97, 123)] * 2 cap_letters = [chr(i) for i in range(65, 91)] * 2 def shift_symbol(symbol, shift): if shift > 26: shift = shift % 26 if symbol.isalpha(): if symbol.isupper(): return cap_letters[cap_letters.index(symbol) + shift] else: return letters[letters.index(symbol) + shift] else: return symbol assert(shift_symbol('z', 28) == 'b') assert(shift_symbol('z', 2) == 'b') assert(shift_symbol('a', 1) == 'b') assert(shift_symbol('A', 1) == 'B') assert(shift_symbol('%', 22) == '%') assert(letters[0] == 'a') assert(letters[-1] == 'z') assert(cap_letters[0] == 'A') assert(cap_letters[-1] == 'Z')

#### Tie together

letters = [chr(i) for i in range(97, 123)] * 2 cap_letters = [chr(i) for i in range(65, 91)] * 2 def shift_symbol(symbol, shift): if shift > 26: shift = shift % 26 if symbol.isalpha(): if symbol.isupper(): return cap_letters[cap_letters.index(symbol) + shift] else: return letters[letters.index(symbol) + shift] else: return symbol def encode_str(string, shift): result = [] for letter in string: result.append(shift_symbol(letter, shift)) return ''.join(result) def decode(arr): #your code pass assert(encode_str('AaBb #$!', 1) == 'BbCc #$!')

## #5 Did I Finish my Sudoku?

### Description

Write a function done_or_not passing a board (list[list_lines]) as parameter. If the board is valid return 'Finished!', otherwise return 'Try again!'

Sudoku rules:

Complete the Sudoku puzzle so that each and every row, column, and region contains the numbers one through nine only once.

Rows:

There are 9 rows in a traditional Sudoku puzzle. Every row must contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9. There may not be any duplicate numbers in any row. In other words, there can not be any rows that are identical.

In the illustration the numbers 5, 3, 1, and 2 are the "givens". They can not be changed. The remaining numbers in black are the numbers that you fill in to complete the row.

Columns:

There are 9 columns in a traditional Sudoku puzzle. Like the Sudoku rule for rows, every column must also contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9. Again, there may not be any duplicate numbers in any column. Each column will be unique as a result.

In the illustration the numbers 7, 2, and 6 are the "givens". They can not be changed. You fill in the remaining numbers as shown in black to complete the column.

Regions

A region is a 3x3 box like the one shown to the left. There are 9 regions in a traditional Sudoku puzzle.

Like the Sudoku requirements for rows and columns, every region must also contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9. Duplicate numbers are not permitted in any region. Each region will differ from the other regions.

In the illustration the numbers 1, 2, and 8 are the "givens". They can not be changed. Fill in the remaining numbers as shown in black to complete the region.

### Solution

#### Appropriate view

def done_or_not(board): #board[i][j] # your solution here # .. # return 'Finished!' # .. # or return 'Try again!'

#### Test suite

valid = [ [1, 3, 2, 5, 7, 9, 4, 6, 8], [4, 9, 8, 2, 6, 1, 3, 7, 5], [7, 5, 6, 3, 8, 4, 2, 1, 9], [6, 4, 3, 1, 5, 8, 7, 9, 2], [5, 2, 1, 7, 9, 3, 8, 4, 6], [9, 8, 7, 4, 2, 6, 5, 3, 1], [2, 1, 4, 9, 3, 5, 6, 8, 7], [3, 6, 5, 8, 1, 7, 9, 2, 4], [8, 7, 9, 6, 4, 2, 1, 5, 3]] assert(done_or_not(valid) == 'Finished!') corrupted = [ [1, 3, 2, 5, 7, 9, 4, 6, 8], [4, 9, 8, 2, 6, 1, 3, 7, 5], [7, 5, 6, 3, 8, 4, 2, 1, 9], [6, 4, 3, 1, 5, 8, 7, 9, 2], [5, 2, 1, 7, 9, 3, 8, 4, 6], [9, 8, 7, 4, 2, 6, 5, 3, 1], [2, 1, 4, 9, 3, 5, 6, 8, 7], [3, 6, 5, 8, 1, 7, 9, 2, 4], [8, 7, 9, 6, 4, 2, 1, 3, 5]] assert(done_or_not(corrupted) == 'Try again!');

#### Common values

gauge = [i for i in range(1, 10)]

#### Check the nine elements

def check_the_nine(nine): if set(nine) == set(gauge): return True else: return False assert(check_the_nine([1, 2, 3, 4, 5, 6, 7, 8, 9]) == True) assert(check_the_nine([1, 2, 3, 4, 5, 6, 7, 2, 9]) == False)

#### Compose nine elements

##### Rows

def check_rows(ll): for i in ll: if check_the_nine(i): continue else: return False else: return True assert(check_rows(valid) == True) assert(check_rows(corrupted) == True)

##### Columns

def check_columns(ll): for i in range(9): nine = [] for j in ll: nine.append(j[i]) if not check_the_nine(nine): return False return True assert(check_columns(valid) == True) assert(check_columns(corrupted) == False)

##### Rectangles 3 X 3

- Extract these rectangles by its leftmost upper corner
def extract_rectangle(ll, x, y): l = [] for i in range(x, x+3): for j in range(y, y+3): l.append(ll[i][j]) return l assert(extract_rectangle(valid, 0, 0) == [1, 3, 2, 4, 9, 8, 7, 5, 6]) assert(extract_rectangle(valid, 3, 3) == [1, 5, 8, 7, 9, 3, 4, 2, 6])

- After that lets iterate all corners in this matrix
def define_corners(): corners = [] for i in range(0, 9, 3): for j in range(0, 9, 3): corners.append([i, j]) return corners print('\n', define_corners())

... ... ... ... ... >>> [[0, 0], [0, 3], [0, 6], [3, 0], [3, 3], [3, 6], [6, 0], [6, 3], [6, 6]]

### Final solution

gauge = [i for i in range(1, 10)] def check_the_nine(nine): if set(nine) == set(gauge): return True else: return False def check_rows(ll): for i in ll: if check_the_nine(i): continue else: return False else: return True def check_columns(ll): for i in range(9): nine = [] for j in ll: nine.append(j[i]) if not check_the_nine(nine): return False return True def extract_rectangle(ll, x, y): l = [] for i in range(x, x+3): for j in range(y, y+3): l.append(ll[i][j]) return l def define_corners(): corners = [] for i in range(0, 9, 3): for j in range(0, 9, 3): corners.append([i, j]) return corners def done_or_not(board): result = True for i in define_corners(): if not check_the_nine(extract_rectangle(board, i[0], i[1])): result = False if check_columns(board) == False or check_rows(board) == False: result = False if result: return 'Finished!' else: return 'Try again!' assert(done_or_not(valid) == 'Finished!') assert(done_or_not(corrupted) == 'Try again!')

## TODO #6 Vigenère Autokey Cipher Helper

### Description

The Vigenère cipher is a classic cipher originally developed by Italian cryptographer Giovan Battista Bellaso and published in 1553. It is named after a later French cryptographer Blaise de Vigenère, who had developed a stronger autokey cipher (a cipher that incorporates the message of the text into the key). In this kata, we're implementing Vigenère's autokey cipher.

The cipher is easy to understand and implement, but survived three centuries of attempts to break it, earning it the nickname "le chiffre indéchiffrable" or "the indecipherable c ipher."

From Wikipedia:

The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution. (…)

In a Caesar cipher, each letter of the alphabet is shifted along some number of places;

for example, in a Caesar cipher of shift 3, A would become D, B would become E, Y would become B and so on. The Vigenère c ipher consists of several Caesar ciphers in sequence with different shift values. The shift is derived by applying a Caesar shift to a character with the corresponding index of the key in the alphabet.

With the basic Vigenère Cipher, we assume the key is repeated for the length of the text, character by character. In this kata, the key is only used once, and then replaced by the decoded text. Every encoding and decoding is independent (still using the same key to begin with). Unlike the Vigenère Cipher Helper kata, the key index is only incremented if the current letter is in the provided alphabet.

Visual representation (suggested by OverZealous):

message: my secret code i want to secure key: pa ssword myse c retc od eiwant

Write a class that, when given a key and an alphabet, can be used to encode and decode from the cipher.

E.g.

alphabet = 'abcdefghijklmnopqrstuvwxyz' key = 'password'

c = VigenereCipher(key, alphabet)

c.encode('codewars'); # returns 'rovwsoiv' c.decode('laxxhsj'); # returns 'waffles'

c.encode('amazingly few discotheques provide jukeboxes')

c.decode('pmsrebxoy rev lvynmylatcwu dkvzyxi bjbsaib') Any character not in the alphabet should be left alone.

c.encode('CODEWARS') # returns 'CODEWARS'

### Solution

#### Appropriate form

alphabet = 'abcdefghijklmnopqrstuvwxyz' key = 'password' class VigenereCipher(object): def __init__(self, key, alphabet): self.key = key self.alphabet = alphabet def special_zip(self, message, satellite): # shift the lerrer implementation with # additional array of values pass def satellite(self, message): # compose a satellite array with shift values # for each symbol in the input message pass def encode(self, message): result = self.special_zip(message, self.satellite(message)) return result def decode(self, message): return message[::-1]

#### Test suite

# creates a cipher helper with each letter substituted # by the corresponding character in the key c = VigenereCipher(key, alphabet) print(c.encode('codewars')) # returns 'rovwsoiv' #.decode('laxxhsj' ) returns 'waffles' print(c.decode('laxxhsj')) # returns 'pmsrebxoy rev lvynmylatcwu dkvzyxi bjbsaib' # c.encode('amazingly few discotheques provide jukeboxes') # # returns 'amazingly few discotheques provide jukeboxes' # c.decode('pmsrebxoy rev lvynmylatcwu dkvzyxi bjbsaib') # Any character not in the alphabet should be left alone. # c.encode('CODEWARS') # returns 'CODEWARS'

... >>> None ... jshxxal

#### Test a particular case with equal lenght pass and message

alphabet = 'abcdefghijklmnopqrstuvwxyz' * 2 key = 'password' message = 'codewars' assert(alphabet[alphabet.index(message[0]) + alphabet.index(key[0])] == 'r') assert(alphabet[alphabet.index(message[1]) + alphabet.index(key[1])] == 'o') assert(alphabet[alphabet.index(message[2]) + alphabet.index(key[2])] == 'v') assert(alphabet[alphabet.index(message[4]) + alphabet.index(key[4])] == 's') #assert(encode('codewars') == 'rovwsoiv')

#### Decoding sample

cipher = 'laxxhsj' rev_alphabet = alphabet[::-1] assert(rev_alphabet[rev_alphabet.index(cipher[0]) + alphabet.index(key[0])] == 'w') assert(rev_alphabet[rev_alphabet.index(cipher[1]) + alphabet.index(key[1])] == 'a')

#### Dynamic shift satellite array

Lets create the list with len(message) which contains the nunmbers corresponding shift value for every single symbol in the message. But when some particular symbol isn't in the alphabet, the shift is zero and this symbol not changed at all.

## DONE #7 Human readable duration format

### Description

Your task in order to complete this Kata is to write a function which formats a duration, given as a number of seconds, in a human-friendly way.

The function must accept a non-negative integer. If it is zero, it just returns "now". Otherwise, the duration is expressed as a combination of years, days, hours, minutes and seconds.

It is much easier to understand with an example:

format_duration(62) # returns "1 minute and 2 seconds" format_duration(3662) # returns "1 hour, 1 minute and 2 seconds"

Note that spaces are important. Detailed rules

The resulting expression is made of components like 4 seconds, 1 year, etc. In general, a positive integer and one of the valid units of time, separated by a space. The unit of time is used in plural if the integer is greater than 1.

The components are separated by a comma and a space (", "). Except the last component, which is separated by " and ", just like it would be written in English.

A more significant units of time will occur before than a least significant one. Therefore, 1 second and 1 year is not correct, but 1 year and 1 second is.

Different components have different unit of times. So there is not repeated units like in 5 seconds and 1 second.

A component will not appear at all if its value happens to be zero. Hence, 1 minute and 0 seconds is not valid, but it should be just 1 minute.

A unit of time must be used "as much as possible". It means that the function should not return 61 seconds, but 1 minute and 1 second instead. Formally, the duration specified by of a component must not be greater than any valid more significant unit of time.

For the purpose of this Kata, a year is 365 days and a day is 24 hours.

## TODO #8 Battleship field validator

### Description

Write a method that takes a field for well-known board game "Battleship" as an argument and returns true if it has a valid disposition of ships, false otherwise. Argument is guaranteed to be 10*10 two-dimension array. Elements in the array are numbers, 0 if the cell is free and 1 if occupied by ship.

Battleship (also Battleships or Sea Battle) is a guessing game for two players. Each player has a 10x10 grid containing several "ships" and objective is to destroy enemy's forces by targetting individual cells on his field. The ship occupies one or more cells in the grid. Size and number of ships may differ from version to version. In this kata we will use Soviet/Russian version of the game.

Before the game begins, players set up the board and place the ships accordingly to the following rules:

- There must be single battleship (size of 4 cells), 2 cruisers (size 3), 3 destroyers (size 2) and 4 submarines (size 1). Any additional ships are not allowed, as well as missing ships.
- Each ship must be a straight line, except for submarines, which are just single cell.
- The ship cannot overlap or be in contact with any other ship, neither by edge nor by corner.

### Appropriate solution form

def validateBattlefield(field): # write your magic here return True battleField = [[1, 0, 0, 0, 0, 1, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 0, 1, 0], [1, 0, 1, 0, 1, 1, 1, 0, 1, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] Test.assert_equals(validateBattlefield(battleField), True, "Yep! Seems alright", "Nope, something is wrong!");

## TODO #9 Instant Runoff Voting

### Description

Your task is to implement a function that calculates an election winner from a list of voter selections using an Instant Runoff Voting algorithm. If you haven't heard of IRV, here's a basic overview (slightly altered for this kata):

- Each voter selects several candidates in order of preference.
- The votes are tallied from the each voter's first choice.
- If the first-place candidate has more than half the total votes, they win.
- Otherwise, find the candidate who got the least votes and remove them from each person's voting list.
- In case of a tie for least, remove all of the tying candidates.
- In case of a complete tie between every candidate, return nil(Ruby)/None(Python)/undefined(JS).
Start over. Continue until somebody has more than half the votes; they are the winner.

Your function will be given a list of voter ballots; each ballot will be a list of candidates (symbols) in descending order of preference. You should return the symbol corresponding to the winning candidate. See the default test for an example!

### Appropriate solution format

def first_place_leader_check(bulletins): leaders = [i[0] for i in bulletins] if len(set(leaders)) <= len(bulletins) // 2 + 1: # leader(s) exist(s) already return True else: # no leader there return False def count_each_candidate(bulletins): # join list of lists together: all_candidates = [j for i in bulletins for j in i] candidates = set(all_candidates) counter = {} for i in candidates: counter[i] = all_candidates.count(i) return counter def runoff(voters): pass voters = [["dem", "ind", "rep"], ["rep", "ind", "dem"], ["ind", "dem", "rep"], ["ind", "rep", "dem"]] assert(count_each_candidate(voters) == {"dem": 4, "ind": 4, "rep": 4}) assert(first_place_leader_check(voters) == True) # Test.assert_equals(runoff(voters), "ind") voters = [["a", "c", "d", "e", "b"], ["e", "b", "d", "c", "a"], ["d", "e", "c", "a", "b"], ["c", "e", "d", "b", "a"], ["b", "e", "a", "c", "d"]]; # Test.assert_equals(runoff(voters), None); assert(first_place_leader_check(voters) == False)

## DONE #10 Base64 Numeric Translator

### Description

Our standard numbering system is (Base 10). That includes 0 through 9. Binary is (Base 2), only 1’s and 0’s. And Hexadecimal is (Base 16) (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). A hexadecimal “F” has a (Base 10) value of 15. (Base 64) has 64 individual characters which translate in value in (Base 10) from between 0 to 63. Write a method that will convert a string from (Base 64) to it's (Base 10) integer value.

The (Base 64) characters from least to greatest will be

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Where 'A' is equal to 0 and '/' is equal to 63.

Just as in standard (Base 10) when you get to the highest individual integer 9 the next number adds an additional place and starts at the beginning 10; so also (Base 64) when you get to the 63rd digit '/' and the next number adds an additional place and starts at the beginning "BA".

Example:

base64_to_base10("/") # => 63 base64_to_base10("BA") # => 64 base64_to_base10("BB") # => 65 base64_to_base10("BC") # => 66

Write a method base64_to_base10 that will take a string (Base 64) number and output it's (Base 10) value as an integer.

### Appropriate solution format

def converter(order, symbol): s = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" number = s.index(symbol) return number * 64 ** order def base64_to_base10(str): sigma = 0 for order, symbol in enumerate(str[::-1]): sigma += converter(order, symbol) return sigma assert(converter(0, 'A') == 0) assert(converter(1, 'B') == 64) assert(base64_to_base10("A") == 0) assert(base64_to_base10("/") == 63) assert(base64_to_base10("BA") == 64) assert(base64_to_base10("//") == 4095) assert(base64_to_base10("WIN") == 90637)

None

### General considerations

For any *positional* numeric system with base b:
xyz = x*b**2 + y*b**1 + z*b**0

## TODO #11 Elementary Arithmetic - Carries Count

### Description

In elementary arithmetic a "carry" is a digit that is transferred from one column of digits to another column of more significant digits during a calculation algorithm.

This Kata is about determining the number of carries performed during the addition of multi-digit numbers.

You will receive an input string containing a set of pairs of numbers formatted as follows:

123 456 555 555 123 594

And your output should be a string formatted as follows:

No carry operation 3 carry operations 1 carry operations

Some Assumptions

- Assume that numbers can be of any length.
- But both numbers in the pair will be of the same length.
- Although not all the numbers in the set need to be of the same length.
- If a number is shorter, it will be zero-padded.
- The input may contain any arbitrary number of pairs.

### Appropriate solution format

def solve(input_string): #your code here Test.assert_equals(solve("123 456\n555 555\n123 594"), "No carry operation\n3 carry operations\n1 carry operations", "Try this one: (123 - 456 | 555 - 555 | 123 - 594)") Test.assert_equals(solve("321 679\n098 805\n123 867"), "3 carry operations\n2 carry operations\n1 carry operations", "Try this one: (321 - 679 | 098 - 805 | 123 - 867)") Test.assert_equals(solve("123 457\n631 372\n999 111"), "1 carry operations\n2 carry operations\n3 carry operations", "Try this one: (123 - 457 | 631 - 372 | 999 - 111)") Test.assert_equals(solve("123 457\n123 456\n654 312\n999 000\n123 457"), "1 carry operations\nNo carry operation\nNo carry operation\nNo carry operation\n1 carry operations","Try this one: (123 - 457 | 123 - 456 | 654 - 312 | 999 - 000 | 123 - 457)") Test.assert_equals(solve("1 9\n123456789 111111101\n01 09\n11 09\n123 457"), "1 carry operations\n1 carry operations\n1 carry operations\n1 carry operations\n1 carry operations", "Try this one: (1 - 9 | 123456789 - 111111101 | 01 - 09 | 11 - 09 | 123 - 457)")

## DONE #12 Valid Parentheses

### Description

Write a function called validParentheses that takes a string of parentheses, and determines if the order of the parentheses is valid. validParentheses should return true if the string is valid, and false if it's invalid.

Examples: validParentheses( "()" ) => returns true validParentheses( ")(()))" ) => returns false validParentheses( "(" ) => returns false validParentheses( "(())((()())())" ) => returns true

All input strings will be nonempty, and will only consist of open parentheses '(' and/or closed parentheses ')'

### Appropriate solution format

def extract_parentheses(string): if string: return [i for i in string if i in '[]{}()'] else: return False def pair(parentheses): if parentheses == ')': return '(' elif parentheses == ']': return '[' elif parentheses == '}': return '{' else: return False def valid_parentheses(string): if string == "": return True else: opening = [] closing = [] parentheses = extract_parentheses(string) if parentheses and len(parentheses) % 2 == 0: for i in parentheses: print(opening, closing) if not pair(i): opening.append(i) print("this is an opening sequence: ", opening) else: try: opening[-1] except IndexError: return False if opening[-1] == pair(i): # annihilate them both try: opening.pop() except IndexError: return False else: # print("The closing parentheses mismatch") # return False closing.append(i) if opening == [] and closing == []: return True else: print('Mismatch in parentheses order') return False else: return False # print(valid_parentheses("hi())(")) # assert(extract_parentheses(")test") == [')']) assert(pair(')') == '(') assert(valid_parentheses(" (") == False) assert(valid_parentheses(")test") == False) assert(valid_parentheses("") == True) assert(valid_parentheses("()()") == True) assert(valid_parentheses("hi())(") == False) assert(valid_parentheses("hi(hi)()") == True) assert(valid_parentheses("[(])") == False)

[] [] this is an opening sequence: ['('] ['('] [] [] [] this is an opening sequence: ['('] ['('] [] [] [] this is an opening sequence: ['('] ['('] [] [] [] [] [] this is an opening sequence: ['('] ['('] [] [] [] this is an opening sequence: ['('] ['('] [] [] [] this is an opening sequence: ['['] ['['] [] this is an opening sequence: ['[', '('] ['[', '('] [] ['[', '('] [']'] Mismatch in parentheses order

## DONE #13 Coordinates Validator

### Description

You need to create a function that will validate if given parameters are valid geographical coordinates.

Valid coordinates look like the following: "23.32353342, -32.543534534". The return value should be either true or false.

Latitude (which is first float) can be between 0 and 90, positive or negative. Longitude (which is second float) can be between 0 and 180, positive or negative.

Coordinates can only contain digits, or one of the following symbols (including space after comma) -, .

There should be no space between the minus "-" sign and the digit after it.

### Appropriate solution

def is_valid_coordinates(coordinates): if 'e' not in coordinates and\ 'E' not in coordinates: try: lat, lon = map(float, coordinates.split(',')) except: return False else: return False print(lat, lon) if lat < -90 or lat > 90: return False if lon < -180 or lon > 180: return False return True valid_coordinates = [ "-23, 25", "4, -3", "24.53525235, 23.45235", "04, -23.234235", "43.91343345, 143"] for coordinate in valid_coordinates: assert is_valid_coordinates(coordinate) == True,\ "%s validation failed." % coordinate invalid_coordinates = [ "23.234, - 23.4234", "2342.43536, 34.324236", "N23.43345, E32.6457", "99.234, 12.324", "6.325624, 43.34345.345", "0, 1,2", "0.342q0832, 1.2324", "23.245, 1e1"] for coordinate in invalid_coordinates: assert is_valid_coordinates(coordinate) == False,\ "%s validation failed." % coordinate

## TODO #14 Pete, the baker

### Description

Pete likes to bake some cakes. He has some recipes and ingredients. Unfortunately he is not good in maths. Can you help him to find out, how many cakes he could bake considering his recipes?

Write a function cakes(), which takes the recipe (object) and the available ingredients (also an object) and returns the maximum number of cakes Pete can bake (integer). For simplicity there are no units for the amounts (e.g. 1 lb of flour or 200 g of sugar are simply 1 or 200). Ingredients that are not present in the objects, can be considered as 0.

Examples:

cakes({flour: 500, sugar: 200, eggs: 1}, {flour: 1200, sugar: 1200, eggs: 5, milk: 200})

cakes({apples: 3, flour: 300, sugar: 150, milk: 100, oil: 100}, {sugar: 500, flour: 2000, milk: 2000})

### Solution

def cakes(recipe, available): # TODO: insert code # test.describe('Testing Pete, the Baker') # test.it('gives us the right number of cakes') recipe = {"flour": 500, "sugar": 200, "eggs": 1} available = {"flour": 1200, "sugar": 1200, "eggs": 5, "milk": 200} # test.assert_equals(cakes(recipe, available), 2, 'Wrong result for example #1') assert(cakes(recipe, available) == 2) recipe = {"apples": 3, "flour": 300, "sugar": 150, "milk": 100, "oil": 100} available = {"sugar": 500, "flour": 2000, "milk": 2000} # test.assert_equals(cakes(recipe, available), 0, 'Wrong result for example #2') assert(cakes(recipe, available) == 0)

## DONE #15 Decode the Morse code

### Description

In this kata you have to write a simple Morse code decoder. While the Morse code is now mostly superceded by voice and digital data communication channels, it still has its use in some applications around the world.

The Morse code encodes every character as a sequence of "dots" and "dashes". For example, the letter A is coded as ·−, letter Q is coded as −−·−, and digit 1 is coded as ·−−−. The Morse code is case-insensitive, traditionally capital letters are used. When the message is written in Morse code, a single space is used to separate the character codes and 3 spaces are used to separate words. For example, the message HEY JUDE in Morse code is ···· · −·−− ·−−− ··− −·· ·.

NOTE: Extra spaces before or after the code have no meaning and should be ignored.

In addition to letters, digits and some punctuation, there are some special service codes, the most notorious of those is the international distress signal SOS (that was first issued by Titanic), that is coded as ···−−−···. These special codes are treated as single special characters, and usually are transmitted as separate words.

Your task is to implement a function decodeMorse(morseCode), that would take the morse code as input and return a decoded human-readable string.

For example:

decodeMorse('…. . -.– .— ..- -.. .') #should return "HEY JUDE"

The Morse code table is preloaded for you as a dictionary, feel free to use it. In CoffeeScript, C++, JavaScript, PHP, Python, Ruby and TypeScript, the table can be accessed like this: MORSE_CODE['.–'], in Java it is MorseCode.get('.–'), in C# it is MorseCode.Get('.–'), in Haskell the codes are in a Map String String and can be accessed like this: morseCodes ! ".–".

All the test strings would contain valid Morse code, so you may skip checking for errors and exceptions. In C#, tests will fail if the solution code throws an exception, please keep that in mind. This is mostly because otherwise the engine would simply ignore the tests, resulting in a "valid" solution.

Good luck!

### Solution

def decodeMorse(morseCode): return morseCode.replace('.', MORSE_CODE['.']).replace('-', MORSE_CODE['-']).replace(' ', '') def testAndPrint(got, expected): if got == expected: test.expect(True) else: print "<pre style='display:inline'>Got '%s', expected '%s'</pre>" % (got, expected) test.expect(False) test.describe("Example from description") testAndPrint(decodeMorse('.... . -.-- .--- ..- -.. .'), 'HEY JUDE') test.describe("Your own tests") # Add more tests here

### Best practice

def decodeMorse(morseCode): return ' '.join(''.join(MORSE_CODE[letter] for letter in word.split(' ')) for word in morseCode.strip().split(' '))

## TODO #16 Next bigger number with the same digits

### Description

You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits:

next_bigger(12)==21 next_bigger(513)==531 next_bigger(2017)==2071 If no bigger number can be composed using those digits, return -1:

next_bigger(9)==-1 next_bigger(111)==-1 next_bigger(531)==-1

### Solution

def next_bigger(n): #your code here Test.assert_equals(next_bigger(12),21) Test.assert_equals(next_bigger(513),531) Test.assert_equals(next_bigger(2017),2071) Test.assert_equals(next_bigger(414),441) Test.assert_equals(next_bigger(144),414)

## DONE #17 Simple fraction to mixed number converter

### Description

Given a string representing a simple fraction x/y, your function must return a string representing the corresponding mixed fraction in the following format:

a b/c

where a is integer part and b/c is irreducible proper fraction. There must be exactly one space between a and b/c.

If the x/y equals the integer part, return integer part only. If integer part is zero, return the irreducible proper fraction only. In both of these cases, the resulting string must not contain any spaces.

Division by zero should raise an error (preferably, the standard zero division error of your language).

Examples

Input: 42/9, expected result: 4 2/3. Input: 6/3, expedted result: 2. Input: 4/6, expected result: 2/3. Input: 0/18891, expected result: 0. Input: -10/7, expected result: -1 3/7. Inputs 0/0 or 3/0 must raise a zero division error. Note

Make sure not to modify the input of your function in-place, it is a bad practice.

### Fraction stdlib module

from fractions import Fractions, gcd """ >>> a = Fraction() >>> a + Fraction(1, 2) Fraction(1, 2) >>> a += Fraction(1, 2) >>> a Fraction(1, 2) >>> Fraction(42, 9) Fraction(14, 3) >>> Fraction(-10, 7) Fraction(-10, 7) >>> Fraction(42, 9).__floor__() 4 >>> Fraction(42, 9).__ceil__() 5 >>> Fraction(0, 7) Fraction(0, 1) >>> Fraction(0, 7).__ceil__() 0 >>> Fraction(1, 7).__ceil__() 1 >>> Fraction(-1, 7).__ceil__() 0 """

### Solution

from fractions import Fraction def mixed_fraction(s): n, d = map(int, s.split('/')) if n != 0: if d != 0: if n * d > 0: signature = True else: signature = False F = Fraction(abs(n), abs(d)) n = F.numerator d = F.denominator if n < d: if signature: return str(n) + '/' + str(d) else: return '-' + str(n) + '/' + str(d) else: # integer part exists integer_part = F.__floor__() fraction_part = n - d * integer_part if fraction_part == 0: if signature: return str(integer_part) else: return '-' + str(integer_part) else: # fraction part exists also fraction_part = Fraction(fraction_part, d) result = str(integer_part) + ' ' + \ str(fraction_part.numerator) + \ '/' + str(fraction_part.denominator) if signature: return result else: return '-' + result else: raise Exception("Must raise ZeroDivisionError") else: return '0' # print(mixed_fraction('6/3')) # print(mixed_fraction('-22/-7')) # assert(simplify(8, 12) == '2/3') # assert(simplify(-8, 12) == '-2/3') # assert(gcd(2, 3) == 1) # assert(gcd(14, 21) == 7) # assert(gcd(-14, 21) == 7) # assert(gcd(12, 144) == 12) assert(mixed_fraction('42/9') == '4 2/3') assert(mixed_fraction('-42/9') == '-4 2/3') assert(mixed_fraction('6/3') == '2') assert(mixed_fraction('-6/3') == '-2') assert(mixed_fraction('4/6') == '2/3') assert(mixed_fraction('-4/6') == '-2/3') assert(mixed_fraction('0/18891') == '0') assert(mixed_fraction('10/7') == '1 3/7') assert(mixed_fraction('-22/-7') == '3 1/7') # assert(mixed_fraction('-10/7') == '-1 3/7') # Test.expect_error("Must raise ZeroDivisionError", lambda: mixed_fraction(0, 0)) # Test.expect_error("Must raise ZeroDivisionError", lambda: mixed_fraction(3, 0))

## TODO #18 Common denominator

### Description

You will have a list of rationals in the form

[ [numer_1, denom_1] , … [numer_n, denom_n] ]

where all numbers are positive ints.

You have to produce a result in the form

[ [N_1, D] … [N_n, D] ]

in which D is as small as possible and

N_1/D

`= numer_1/denom_1 ... N_n/D =`

numer_n,/denom_n.Example:

convertFracs [(1, 2), (1, 3), (1, 4)] `shouldBe` [(6, 12), (4, 12), (3, 12)]

### Solution

from fractions import Fraction, gcd def gcdl(L): result = L[0] for i in L[1::]: result = gcd(result, i) return result def convertFracts(lst): pass # divisors = [i[1] for i in lst] # numerators = [i[0] for i in lst] # if gcdl(divisors) == 1: # common_divisor = 1 # reduce(lambda x, y: x*y, divisors) # for i in divisors: # common_divisor *= i # result = [] # for n, d in zip(numerators, divisors): # print(n, d, common_divisor) # result.append([n * common_divisor / d, common_divisor]) # print(result) # return result # else: # pass # assert(convertFracts([(1, 2), (1, 3), (1, 4)]) == # [(6, 12), (4, 12), (3, 12)]) # assert(convertFracts([[361560, 681200], # [45240, 681200], # [510900, 681200]]) == # [[18078, 34060], # [2262, 34060], # [25545, 34060]]) assert(gcd(12, 4) == 4) assert(gcdl([6, 12, 36]) == 6) assert(gcdl([1, 2, 3]) == 1) assert(gcdl([361560, 681200, 45240, 510900]) == 20)

## DONE #19 Strip Url Params

### Description

Complete the method so that it does the following:

- Removes any duplicate query string parameters from the url
- Removes any query string parameters specified within the 2nd argument (optional array)
Examples:

stripUrlParams('www.codewars.com?a=1&b=2&a=2')

/ returns 'www.codewars.com?a=1&b=2' stripUrlParams('www.codewars.com?a=1&b=2&a=2', ['b']) /returns 'www.codewars.com?a=1' stripUrlParams('www.codewars.com', ['b']) // returns 'www.codewars.com'

### Solution

- Split into header and arguments
- Split arguments into key=value pairs
- Iterate each pair

def strip_url_params(url, params_to_strip = []): try: header, tail = url.split('?') except ValueError: return url arguments = tail.split('&') result_arguments = [] keys = [] for i in arguments: key, value = i.split('=') if key not in keys and key not in params_to_strip: keys.append(key) result_arguments.append(i) else: continue return header + '?' + '&'.join(result_arguments) assert(strip_url_params('www.codewars.com?a=1&b=2&a=2') == 'www.codewars.com?a=1&b=2') assert(strip_url_params('www.codewars.com?a=1&a=2') == 'www.codewars.com?a=1') assert(strip_url_params('www.codewars.com?a=1&b=2&a=2', ['b']) == 'www.codewars.com?a=1') assert(strip_url_params('www.codewars.com', ['b']) == 'www.codewars.com')

## DONE #20 Strip Comments

### Description

Complete the solution so that it strips all text that follows any of a set of comment markers passed in. Any whitespace at the end of the line should also be stripped out.

Example:

Given an input string of:

apples, pears # and bananas grapes bananas !apples

The output expected would be:

apples, pears grapes bananas

The code would be called like so:

result = solution("apples, pears # and bananas\ngrapes\nbananas !apples", ["#", "!"])

### Solution

def symbol_in_string(s, symbols): result = False for i in symbols: if i in s: result = True break return result def find_first_marker(s, markers): if symbol_in_string(s, markers): for i in markers: position = len(s) marker = '' new_position = s.find(i) if new_position != -1 and new_position < position: marker = i position = new_position return marker else: # no stop symbol there return False def solution(txt, markers): try: strings = txt.split('\n') except: # one string only strings = [] + [txt] # result = [] # for i in strings: # stop_points = [] # for j in markers: # try: # point = i.find(j) # pass assert(symbol_in_string('ABCD', ['a', 'b', 'c']) == False) assert(symbol_in_string('ABCD', ['a', 'A', 'B']) == True) print(find_first_marker('Abcd@#, !, $', ['!', '#', '$'])) assert(find_first_marker('Abcd@#, !, $', ['!', '$', '#']) == '#') assert(find_first_marker('Abcd@#, !, $', ['2', '1', '3']) == False) assert(find_first_marker('Abcd@#, !, $', ['!', '#', '$']) == '#') # assert(solution("apples, pears # and bananas\ngrapes\nbananas !apples", ["#", "!"]) == "apples, pears\ngrapes\nbananas") # assert(solution("a #b\nc\nd $e f g", ["#", "$"]) == "a\nc\nd")

## DONE #21 RGB To Hex Conversion

### Description

The rgb() method is incomplete. Complete the method so that passing in RGB decimal values will result in a hexadecimal representation being returned. The valid decimal values for RGB are 0 - 255. Any (r,g,b) argument values that fall out of that range should be rounded to the closest valid value.

The following are examples of expected output values:

rgb(255, 255, 255) # returns FFFFFF rgb(255, 255, 300) # returns FFFFFF rgb(0,0,0) # returns 000000 rgb(148, 0, 211) # returns 9400D3

### Solution

def convert_value(n): """ from 0 to 255 """ if n < 0: return '00' elif n > 255: return 'FF' else: result = hex(n)[2:].upper() if n > 15: return result else: return '0' + result def rgb(r, g, b): norm_rgb = map(convert_value, [r, g, b]) #your code here :) return ''.join(norm_rgb) assert(convert_value(-1) == '00') assert(convert_value(255) == 'FF') assert(convert_value(300) == 'FF') assert(rgb(0,0,0) == "000000") assert(rgb(1,2,3) == "010203") assert(rgb(255,255,255) == "FFFFFF") assert(rgb(254,253,252) == "FEFDFC") assert(rgb(-20,275,125) == "00FF7D")

## DONE #22 Calculator

### Description

Create a simple calculator that given a string of operators (+ - * and /) and numbers separated by spaces returns the value of that expression

Example:

Calculator().evaluate("2 / 2 + 3 * 4 - 6") # => 7 Remember about the order of operations! Multiplications and divisions have a higher priority and should be performed left-to-right. Additions and subtractions have a lower priority and should also be performed left-to-right.

### Solution

class Calculator(object): def evaluate(self, string): result = eval(string) if str(result)[-1] != 0: return round(result, 5) else: return int(result) assert(Calculator().evaluate("2 / 2 + 3 * 4 - 6") == 7)

## TODO #23 Twice linear

### Description

Consider a sequence u where u is defined as follows:

The number u(0) = 1 is the first one in u. For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too. There are no other numbers in u. Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, …]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on…

Task:

Given parameter n the function dbl_linear (or dblLinear…) returns the element u(n) of the ordered (with <) sequence u.

Example:

dbl_linear(10) should return 22

Note:

Focus attention on efficiency

### Solution

def f2(k): return 2 * k + 1 def f3(k): return 3 * k + 1 def visualize(n): result = [1] while len(result) < n: result.append(f2(result[-1])) result.append(f3(result[-2])) result.append(f2(result[-2])) result.append(f2(result[-2])) result.append(f3(result[-4])) result.append(f3(result[-4])) result.append(f2(result[-4])) result.append(f2(result[-4])) # result = [1] # for i in range(n)[1:]: # result.append(f2(i)) # result.append(f3(i)) return result def dbl_linear(n): """ y = 2 * x + 1 and z = 3 * x + 1 u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...] u[1, 3, 5 ...] = function(2) u[2, 4, 6 ...] = function(3) """ if n != 0: if n % 2: # result is function of 3 k = n // 3 else: # result is function of 2 pass else: return 1 print(visualize(5)) u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27] assert(u[10] == 22) assert(dbl_linear(0) == 1) # assert(dbl_linear(10) == 22)

[1, 3, 4, 5, 7, 7, 10, 9, 13, 11, 16, 13, 19, 15, 22, 17, 25, 19, 28]

## TODO #24 Molecule to atoms

### Description

For a given chemical formula represented by a string, count the number of atoms of each element contained in the molecule and return an object.

For example:

water = 'H2O' parse_molecule(water) # return {H: 2, O: 1}

magnesium_hydroxide = 'Mg(OH)2' parse_molecule(magnesium_hydroxide) # return {Mg: 1, O: 2, H: 2}

var fremy_salt = 'K4[ON(SO3)2]2' parse_molecule(fremySalt) # return {K: 4, O: 14, N: 2, S: 4}

As you can see, some formulas have brackets in them. The index outside the brackets tells you that you have to multiply count of each atom inside the bracket on this index. For example, in Fe(NO3)2 you have one iron atom, two nitrogen atoms and six oxygen atoms.

Note that brackets may be round, square or curly and can also be nested. Index after the braces is optional.

### Solution

def parse_molecule (formula): pass assert(parse_molecule("H2O") == {'H': 2, 'O' : 1}) assert(parse_molecule("Mg(OH)2") == {'Mg': 1, 'O' : 2, 'H': 2}) assert(parse_molecule("K4[ON(SO3)2]2") == {'K': 4, 'O': 14, 'N': 2, 'S': 4})

## TODO #25 Next bigger number with the same digits

### Description

You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits:

next_bigger(12)==21 next_bigger(513)==531 next_bigger(2017)==2071

If no bigger number can be composed using those digits, return -1:

next_bigger(9)==-1 next_bigger(111)==-1 next_bigger(531)==-1

### Solution

def regr(digits): previous = digits[0] for i in digits[1:]: if i > previous: return True else: previous = i return False assert(regr([5, 3, 1]) == False) assert(regr([1, 1, 1]) == False) assert(regr([5, 3, 7, 1]) == True) assert(regr([5, 3, 1, 2]) == True) assert(regr([9, 7, 5, 4, 6]) == True) assert(regr([9, 7, 4, 5, 6]) == True) def argument_valid(num): if num > 11: digits = [int(i) for i in str(num)] if len(set(digits)) == 1: return False elif regr(digits): return True else: return False return False assert(argument_valid(5371)) assert(argument_valid(5312)) assert(argument_valid(5661)) def palindrome(n): return int(str(n)[::-1]) assert(palindrome(321) == 123) def next_bigger(n): if argument_valid(n): """ swap on the edge """ N = str(palindrome(n)) k = int(N[0]) for i in N[1:]: if k > int(i): # detect the peak return (k, int(i)) else: return -1 assert(next_bigger(9) == -1) assert(next_bigger(111) == -1) assert(next_bigger(531) == -1) assert(next_bigger(513) == (3, 1)) # assert(next_bigger(12) == 21) # assert(next_bigger(513) == 531) # assert(next_bigger(2017) == 2071) # assert(next_bigger(414) == 441) # assert(next_bigger(144) == 414)

## DONE #26 Catching Car Mileage Numbers

### Description

"7777…8?!??!", exclaimed Bob, "I missed it again! Argh!" Every time there's an interesting number coming up, he notices and then promptly forgets. Who doesn't like catching those one-off interesting mileage numbers? Let's make it so Bob never misses another interesting number. We've hacked into his car's computer, and we have a box hooked up that reads mileage numbers. We've got a box glued to his dash that lights up yellow or green depending on whether it receives a 1 or a 2 (respectively).

It's up to you, intrepid warrior, to glue the parts together. Write the function that parses the mileage number input, and returns a 2 if the number is "interesting" (see below), a 1 if an interesting number occurs within the next two miles, or a 0 if the number is not interesting.

"Interesting" Numbers

Interesting numbers are 3-or-more digit numbers that meet one or more of the following criteria:

Any digit followed by all zeros: 100, 90000 Every digit is the same number: 1111 The digits are sequential, incementing†: 1234 The digits are sequential, decrementing‡: 4321 The digits are a palindrome: 1221 or 73837 The digits match one of the values in the awesomePhrases array † For incrementing sequences, 0 should come after 9, and not before 1, as in 7890. ‡ For decrementing sequences, 0 should come after 1, and not before 9, as in 3210. So, you should expect these inputs and outputs:

is_interesting(3, [1337, 256]) # 0 is_interesting(3236, [1337, 256]) # 0

is_interesting(11207, []) # 0 is_interesting(11208, []) # 0 is_interesting(11209, []) # 1 is_interesting(11210, []) # 1 is_interesting(11211, []) # 2

is_interesting(1335, [1337, 256]) # 1 is_interesting(1336, [1337, 256]) # 1 is_interesting(1337, [1337, 256]) # 2 Error Checking

A number is only interesting if it is greater than 99! Input will always be an integer greater than 0, and less than 1,000,000,000. The awesomePhrases array will always be provided, and will always be an array, but may be empty. (Not everyone thinks numbers spell funny words…) You should only ever output 0, 1, or 2.

### Solution

def num_checker(n): check_list = [zero_check, single_num_check, incrementing_seq_check, decrementing_seq_check, palindrome_check] for f in check_list: if f(n): return True return False def zero_check(n): """ Any digit followed by all zeros: 100, 90000 """ if set(str(n)[1:]) == set('0'): return True else: return False def single_num_check(n): """ Every digit is the same number: 1111 """ if len(set(str(n))) == 1: return True else: return False def incrementing_seq_check(n): """ The digits are sequential, incementing†: 1234 For incrementing sequences, 0 should come after 9, and not before 1, as in 7890. """ seq = '1234567890' if str(n) in seq: return True else: return False def decrementing_seq_check(n): """ The digits are sequential, decrementing‡: 4321 For decrementing sequences, 0 should come after 1, and not before 9, as in 3210 """ seq = '9876543210' if str(n) in seq: return True else: return False def palindrome_check(n): """ The digits are a palindrome: 1221 or 73837 """ if str(n) == str(n)[::-1]: return True else: return False def is_interesting(number, awesome_phrases): if number > 99: if awesome_phrases: for i in awesome_phrases: if number == i: return 2 elif number + 1 == i: return 1 if num_checker(number): return 2 if num_checker(number + 1): return 1 else: return 0 return 0 assert(num_checker(87654) == True) assert(num_checker(12321) == True) assert(palindrome_check(12321) == True) assert(decrementing_seq_check(9875) == False) assert(decrementing_seq_check(987) == True) assert(incrementing_seq_check(123457) == False) assert(incrementing_seq_check(12345) == True) assert(single_num_check(1111) == True) assert(single_num_check(1011) == False) assert(zero_check(310) == False) assert(zero_check(300) == True) assert(is_interesting(330, []) == 0) assert(is_interesting(331, []) == 0) assert(is_interesting(3, [1337, 256]) == 0) assert(is_interesting(1336, [1337, 256]) == 1) assert(is_interesting(1337, [1337, 256]) == 2) assert(is_interesting(11211, [1337, 256]) == 2) # test.describe("Basic inputs") # test.it("should work, dangit!") # tests = [ # {'n': 3, 'interesting': [1337, 256], 'expected': 0}, # {'n': 1336, 'interesting': [1337, 256], 'expected': 1}, # {'n': 1337, 'interesting': [1337, 256], 'expected': 2}, # {'n': 11208, 'interesting': [1337, 256], 'expected': 0}, # {'n': 11209, 'interesting': [1337, 256], 'expected': 1}, # {'n': 11211, 'interesting': [1337, 256], 'expected': 2}, # ] # for t in tests: # test.assert_equals(is_interesting(t['n'], t['interesting']), t['expected']) """ Interesting numbers are 3-or-more digit numbers that meet one or more of the following criteria: Any digit followed by all zeros: 100, 90000 Every digit is the same number: 1111 The digits are sequential, incementing†: 1234 The digits are sequential, decrementing‡: 4321 The digits are a palindrome: 1221 or 73837 The digits match one of the values in the awesomePhrases array † For incrementing sequences, 0 should come after 9, and not before 1, as in 7890. ‡ For decrementing sequences, 0 should come after 1, and not before 9, as in 3210. """

## TODO #27 Finding an appointment

### Description

The businesspeople among you will know that it's often not easy to find an appointment. In this kata we want to find such an appointment automatically. You will be given the calendars of our businessperson and a duration for the meeting. Your task is to find the earliest time, when every businessperson is free for at least that duration.

Example Schedule:

Person | Meetings A | 09:00 - 11:30, 13:30 - 16:00, 16:00 - 17:30, 17:45 - 19:00 B | 09:15 - 12:00, 14:00 - 16:30, 17:00 - 17:30 C | 11:30 - 12:15, 15:00 - 16:30, 17:45 - 19:00

Rules:

- All times in the calendars will be given in 24h format "hh:mm", the result must also be in that format
- A meeting is represented by its start time (inclusively) and end time (exclusively) -> if a meeting takes place from 09:00 - 11:00, the next possible start time would be 11:00
- The businesspeople work from 09:00 (inclusively) - 19:00 (exclusively), the appointment must start and end within that range
- If the meeting does not fit into the schedules, return null or None as result
- The duration of the meeting will be provided as an integer in minutes
Following these rules and looking at the example above the earliest time for a 60 minutes meeting would be 12:15.

### Solution

def get_start_time(schedules, duration): pass # Example from description schedules = [ [['09:00', '11:30'], ['13:30', '16:00'], ['16:00', '17:30'], ['17:45', '19:00']], [['09:15', '12:00'], ['14:00', '16:30'], ['17:00', '17:30']], [['11:30', '12:15'], ['15:00', '16:30'], ['17:45', '19:00']] ] assert(get_start_time(schedules, 60) == '12:15') assert(get_start_time(schedules, 90) == None)

## DONE #28 Scramblies

### Description

Write function scramble(str1,str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.

For example: str1 is 'rkqodlw' and str2 is 'world' the output should return true. str1 is 'cedewaraaossoqqyt' and str2 is 'codewars' should return true. str1 is 'katas' and str2 is 'steak' should return false.

Only lower case letters will be used (a-z). No punctuation or digits will be included. Performance needs to be considered

### Solution

def scramble(s1, s2): for i in set(s2): if s1.count(i) < s2.count(i): return False else: return True assert(scramble('rkqodlw','world') == True) assert(scramble('cedewaraaossoqqyt','codewars') == True) assert(scramble('katas','steak') == False) assert(scramble('scriptjava','javascript') == True) assert(scramble('scriptingjava','javascript') == True)

## TODO #29 IP Validation

### Description

Write an algorithm that will identify valid IPv4 addresses in dot-decimal format. Input to the function is guaranteed to be a single string.

Examples of valid inputs: 1.2.3.4 123.45.67.89

Examples of invalid inputs: 1.2.3 1.2.3.4.5 123.456.78.90 123.045.067.089

### Solution

def is_valid_IP(strng): return None assert(is_valid_IP('12.255.56.1') == True) assert(is_valid_IP('') == False) assert(is_valid_IP('abc.def.ghi.jkl') == False) assert(is_valid_IP('123.456.789.0') == False) assert(is_valid_IP('12.34.56') == False) assert(is_valid_IP('12.34.56 .1') == False) assert(is_valid_IP('12.34.56.-1') == False) assert(is_valid_IP('123.045.067.089') == False)

## TODO #30 Matrix operations

### Description

Matrix rotation π/2 clockwise, n-times (once by default)

### Solution

def matrix_rotate_clockwise(m, n): return list(zip(*m[::-1])) matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] assert(matrix_rotate_clockwise(matrix, 1) == [(7, 4, 1), (8, 5, 2), (9, 6, 3)]) matrix = [ (1, 2, 3), (4, 5, 6), (7, 8, 9) ] assert(matrix_rotate_clockwise(matrix, 1) == [(7, 4, 1), (8, 5, 2), (9, 6, 3)])

## #31 Longest common subsequence

### Description

Write a function called LCS that accepts two sequences, and returns the longest subsequence common to the passed in sequences. Subsequence

A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence. Example subsequence

Subsequences of "abc" = "a", "b", "c", "ab", "ac", "bc" LCS examples

lcs( "abcdef" , "abc" ) => returns "abc" lcs( "abcdef" , "acf" ) => returns "acf" lcs( "132535365" , "123456789" ) => returns "12356"

Notes

Both arguments will be strings Return value must be a string Return an empty string if there exists no common subsequence Both arguments will have one or more characters (in JavaScript)

All tests will only have a single longest common subsequence. Don't worry about cases such as LCS( "1234", "3412" ), which would have two possible longest common subsequences: "12" and "34".

Note that the Haskell variant will use randomized testing, but any longest common subsequence will be valid.

Note that the OCaml variant is using generic lists instead of strings, and will also have randomized tests (any longest common subsequence will be valid).

### Solution

def lcs(long_string, short_string): if short_string in long_string: return short_string result = [] for symbol in short_string: if symbol in long_string: result.append(symbol) return "".join(result) assert(lcs("abcdef" , "abc") == "abc") assert(lcs( "abcdef" , "acf") == "acf") assert(lcs("132535365" , "123456789") =="12356") assert(lcs('a', 'b') == "") # 'notatest' should equal 'nottest'

## #32 Design a Simple Automaton (Finite State Machine)

### Description

Create a finite automaton that has three states. Finite automatons are the same as finite state machines for our purposes.

Our simple automaton, accepts the language of A, defined as {0, 1} and should have three states, q1, q2, and q3.

q1 is our start state. We begin reading commands from here. q2 is our accept state. We return true if this is our last state.

q1 moves to q2 when given a 1, and stays at q1 when given a 0. q2 moves to q3 when given a 0, and stays at q2 when given a 1. q3 moves to q2 when given a 0 or 1.

Our automaton should return whether we end in our accepted state, or not (true/false.)

Here's an example.

a = Automaton()

is_accepted = a.read_commands(["1", "0", "0", "1", "0"])

We make these transitions based on the input of ["1", "0", "0", "1", "0"],

1 q1 -> q2 0 q2 -> q3 0 q3 -> q2 1 q2 -> q2 0 q2 -> q3

We end in q3, which is not our accept state, so return false.

The input of ["1", "0", "0", "1", "0"] would cause us to return false, as we would end in q3.

I have started you off with the bare bones of the Automaton object.

You will have to design your state objects, and how your Automaton handles transitions. Also make sure you set up the three states, q1, q2, and q3, for the myAutomaton instance. The test fixtures will be calling against myAutomaton.

As an aside, the automaton accepts an array of strings, rather than just numbers, or a number represented as a string, because the language an automaton can accept isn't confined to just numbers. An automaton should be able to accept any 'symbol.'

Here are some resources on DFAs (the automaton this Kata asks you to create.)

### Solution

class Automaton(object): def __init__(self): self.state = "q1" # self.state = "q5" def read_commands(self, commands): for i in commands: if i == "1": if self.state == "q1": self.state = "q2" continue if self.state == "q3": self.state = "q2" continue if i == "0": if self.state == "q2": self.state = "q3" continue if self.state == "q3": self.state = "q2" continue if self.state == "q2": return True else: return False my_automaton = Automaton() # Do anything necessary to set up your automaton's states, q1, q2, and # q3. assert(my_automaton.read_commands(["1", "0", "0", "1", "0"]) == False) assert(my_automaton.read_commands(["1"])) assert(my_automaton.read_commands(["1", "0", "0", "1"])) # q1 is our start state. We begin reading commands from here. # q2 is our accept state. We return true if this is our last state. # q1 moves to q2 when given a 1, and stays at q1 when given a 0. # q2 moves to q3 when given a 0, and stays at q2 when given a 1. # q3 moves to q2 when given a 0 or 1.

## #33 Pick peacks

### Description

In this kata, you will write a func that returns the positions and the values of the "peaks" (or local maxima) of a numeric array.

For example, the array arr = [0, 1, 2, 5, 1, 0] has a peak in position 3 with a value of 5 (arr[3] equals 5).

The output will be returned as a struct (PosPeaks) with two properties: Pos and Peaks. Both of these properties should be arrays. If there is no peak in the given array, then the output should be {Pos: [], Peaks: []}.

Example: PickPeaks([3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]) returns {Pos: [3, 7], Peaks: [6, 3]}

All input arrays will be valid numeric arrays (although it could still be empty), so you won't need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don't know what is after and before and therefore, we don't know if it is a peak or not).

Also, beware of plateaus! [1, 2 , 2 , 2 , 1] has a peak while [1, 2, 2, 2, 3] does not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: PickPeaks([1, 2, 2, 2, 1]) returns {Pos: [1], Peaks: [2]}

### Solution

def plateau(arr): pre_previous = arr[0] previous = arr[1] for i in arr[2:]: if i < previous and previous == pre_previous: return True pre_previous = previous previous = 1 return False def pick_peaks(arr): peaks = {"pos":[], "peaks":[]} if len(arr) > 2: for i in range(1, len(arr) - 1): if arr[i] > arr[i+1] and arr[i] > arr[i-1]: peaks["pos"].append(i) peaks["peaks"].append(arr[i]) continue if arr[i] > arr[i-1] and arr[i] == arr[i+1] and plateau(arr[i:]): peaks["pos"].append(i) peaks["peaks"].append(arr[i]) return peaks assert(plateau([2, 2, 2, 1])) assert(plateau([2, 2, 4, 6, 7]) == False) assert(plateau([2, 2, 4, 6, 5]) == False) assert(plateau([2, 2, 2, 2]) == False) print(pick_peaks([1,2,3,6,4,1,2,3,2,1])) ## ('should support finding peaks') assert(pick_peaks([1,2,3,6,4,1,2,3,2,1]) == {"pos":[3,7], "peaks":[6,3]}) ## ('should support finding peaks, but should ignore peaks on the edge ## of the array') assert(pick_peaks([3,2,3,6,4,1,2,3,2,1,2,3]) == {"pos":[3,7], "peaks":[6,3]}) ## ('should support finding peaks; if the peak is a plateau, it should ## only return the position of the first element of the plateau') print(pick_peaks([3,2,3,6,4,1,2,3,2,1,2,2,2,1])) assert(pick_peaks([3,2,3,6,4,1,2,3,2,1,2,2,2,1]) == {"pos":[3,7,10], "peaks":[6,3,2]}) ## ('should support finding peaks; if the peak is a plateau, it should ## only return the position of the first element of the plateau') assert(pick_peaks([2,1,3,1,2,2,2,2,1]) == {"pos":[2,4], "peaks":[3,2]}) ## ('should support finding peaks, but should ignore peaks on the edge ## of the array') # print(pick_peaks([2,1,3,1,2,2,2,2])) assert(pick_peaks([2,1,3,1,2,2,2,2]) == {"pos":[2], "peaks":[3]})

## #34 Permutations

### Description

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:

permutations('a'); # ['a'] permutations('ab'); # ['ab', 'ba'] permutations('aabb'); # ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

The order of the permutations doesn't matter.

### Solution

# result = [] # def permutations(head, tail=''): # if len(head) == 0: result.append(tail) # else: # for i in range(len(head)): # permutations(head[0:i] + head[i+1:], tail+head[i]) # return result def cyclic_shift(s): l = list(s) tail = l.pop() return tail + ''.join(l) assert(cyclic_shift('abc') == 'cab') # assert(permutations('a') == ['a']) # assert(sorted(permutations('ab')) == ['ab', 'ba']) # assert(sorted(permutations('aabb')) == ['aabb', # 'abab', # 'abba', # 'baab', # 'baba', # 'bbaa'])

## #35 Palindrome generator

### Description

Your task is to generate a palindrome string, using the specified length n, the specified characters c(all characters in c must be used at least once), and the code length should less than: python 55 characters javascript 62 characters

### Solution

def palindrome(n, c): pass assert(palindrome(3, ['a', 'b']) == 'aba') assert(palindrome(4, ['a', 'b']) == 'abba')

## #36 The observed PIN

### Description

Alright, detective, one of our colleagues successfully observed our target person, Robby the robber. We followed him to a secret warehouse, where we assume to find all the stolen stuff. The door to this warehouse is secured by an electronic combination lock. Unfortunately our spy isn't sure about the PIN he saw, when Robby entered it. The keypad has the following layout:

┌───┬───┬───┐ │ 1 │ 2 │ 3 │ ├───┼───┼───┤ │ 4 │ 5 │ 6 │ ├───┼───┼───┤ │ 7 │ 8 │ 9 │ └───┼───┼───┘ │ 0 │ └───┘

He noted the PIN 1357, but he also said, it is possible that each of the digits he saw could actually be another adjacent digit (horizontally or vertically, but not diagonally). E.g. instead of the 1 it could also be the 2 or 4. And instead of the 5 it could also be the 2, 4, 6 or 8.

He also mentioned, he knows this kind of locks. You can enter an unlimited amount of wrong PINs, they never finally lock the system or sound the alarm. That's why we can try out all possible (*) variations. possible in sense of: the observed PIN itself and all variations considering the adjacent digits

Can you help us to find all those variations? It would be nice to have a function, that returns an array of all variations for an observed PIN with a length of 1 to 8 digits. We could name the function getPINs (get_pins in python). But please note that all PINs, the observed one and also the results, must be strings, because of potentially leading '0's. We already prepared some test cases for you. Detective, we count on you!

### Solution

def get_pins(observed): '''TODO: This is your job, detective!''' pass test.describe('example tests') expectations = [('8', ['5', '7', '8', '9', '0']), ('11', ["11", "22", "44", "12", "21", "14", "41", "24", "42"]), ('369', ["339", "366", "399", "658", "636", "258", "268", "669", "668", "266", "369", "398", "256", "296", "259", "368", "638", "396", "238", "356", "659", "639", "666", "359", "336", "299", "338", "696", "269", "358", "656", "698", "699", "298", "236", "239"])] for tup in expectations: test.assert_equals(sorted(get_pins(tup[0])), sorted( tup[1]), 'PIN: ' + tup[0])

blog comments powered by Disqus