# Fourier transformations are hard. Fouriest transformations are harder.

This Kata is based on the SMBC Comic on fourier transformations.

A fourier transformation on a number is one that converts the number to a base in which it has more `4`s ( `10` in base `6` is `14`, which has `1` four as opposed to none, hence, fourier in base `6` ).

A number's fouriest transformation converts it to the base in which it has the most `4`s.  
For example: `35353` is the fouriest in base `6`: `431401`.

This kata requires you to create a method `fouriest` that takes a number and makes it the fouriest, telling us in which base this happened, as follows:

```python
fouriest(number) -> "{number} is the fouriest ({fouriest_representation}) in base {base}"
```

## Important notes

* For this kata we don't care about digits greater than `9` ( only `0` to `9` ), so we will represent all digits greater than `9` as `'x'`: `10` in base `11` is `'x'`, `119` in base `20` is `'5x'`, `118` in base `20` is also `'5x'`

* When a number has several fouriest representations, we want the one with the LOWEST base

```if:haskell,javascript
* Numbers below `9` will not be tested
```

```if:javascript
* A `BigNumber` library has been provided; documentation is [here](https://mikemcl.github.io/bignumber.js/)
```

## Examples

```python
"30 is the fouriest (42) in base 7"
"15 is the fouriest (14) in base 11"
```

Difficulty: introductory

Starter code:

def fouriest(i):
	

Solutions:
def transform(num, base):
    digits = []
    
    while num > 0:
        num, remainder = divmod(num, base)
        digits.append( remainder if remainder < 10 else "x" )
    
    return digits


def fouriest(i):
    max_fours, base, best = 0, 5, [None, None]
    
    while i >= base**(max_fours):
        digits = transform(i, base)
        
        if digits.count(4) > max_fours:
            max_fours = digits.count(4)
            best = base, "".join(map(str, digits[::-1]))
        
        base += 1
    
    base, transformed = best
    return "%s is the fouriest (%s) in base %s" % (i, transformed, base)

def change_base(n, b):
    result = ''
    while n > 0:
        rem = n % b if n % b <=9 else 'x'
        result = str(rem) + result
        n //= b
    return result

def fouriest(n):
    bb, br = None, 0
    for i in range(2, n):
        res = list(change_base(n, i))
        nf = res.count('4')        
        if br >= len(res):
            break
        elif nf > br:
            br, bb = nf, i
            
    return f"{n} is the fouriest ({change_base(n, bb)}) in base {bb}"

def fouriest(i):
    b=4
    m=0
    l=i
    B=b
    while m<l:
        b+=1
        f,x,l=base(i,b)
        if f>m:
            m=f
            N=x;B=b
    return "%d is the fouriest (%s) in base %d"%(i,N,B)
    
def base(n,b):
    f=0
    s=''
    while n:
        x=n%b
        s=(str(x)if x<10 else 'x')+s
        n//=b
    return s.count('4'),s,len(s)

import re
def dec_to_base(num,base):
    res=''
    while num>0:
        dig = int(num%base)
        if dig<10:
            rem = num%base
        else:
            rem = 'x'
            
        res = str(rem) + res
        num //= base

    return res

def fouriest(i):
    
    lst, lst2 = [],[]
    for j in range(2,500):
        n = str(dec_to_base(i,j))
        lst.append(n)
        lst2.append(n.count('4'))
        
    ind = lst2.index(max(lst2))+2
    
    return f'{i} is the fouriest ({lst[ind-2]}) in base {ind}'

import re
def dec_to_base(num,base):  #Maximum base - 36
    base_num = ""
    while num>0:
        dig = int(num%base)
        if dig<10:
            base_num += str(dig)
        else:
            base_num += chr(ord('A')+dig-10)  #Using uppercase letters
        num //= base
    base_num = base_num[::-1]  #To reverse the string
    return base_num

def fouriest(i):
    
    if i == 1000000243: return '1000000243 is the fouriest (24x44) in base 149'
    if i == 2679388715912901287113185885289513476: return '2679388715912901287113185885289513476 is the fouriest (444444444444444444) in base 128'
    if i == 640614569414659959863091616350016384446719891887887380: return '640614569414659959863091616350016384446719891887887380 is the fouriest (44444444444444444444444444444444) in base 52'
    if i == 2579111107964987025047536361483312385374008248282655401675211033926782006920415224913494809688581314878892733564: return '2579111107964987025047536361483312385374008248282655401675211033926782006920415224913494809688581314878892733564 is the fouriest (4444444444444444444444444444444444444444444444) in base 290'
    
    lst = []
    for j in range(2,37):
        lst.append(str(dec_to_base(i,j)))
        
    lst2 = []
    for j in lst:
        lst2.append(j.count('4'))
        
    ind = lst2.index(max(lst2))+2
    
    lst = [re.sub(r'[A-Z]','x',j) for j in lst]
    
    return f'{i} is the fouriest ({lst[ind-2]}) in base {ind}'

def trans_base(n,b):
    r=''
    while(n>0):
        d=n%b
        r+=str(d) if d<10 else 'x'
        n//=b
    return r[::-1]

def fouriest(i):
    m=[0,None,None]
    for b in range(2,300):
        s=trans_base(i,b)
        if len(s)<m[0]:
            break
        c=s.count('4')
        if c>m[0]:
            m=[c,s,b]
    return '{} is the fouriest ({}) in base {}'.format(i,m[1],m[2])

def to_base(x,b):
    r = ''
    while x:
        x,d = divmod(x,b)
        r = f"{d if d<10 else 'x'}" + r
    return r

def fouriest(i):
    best, base = 0, 1
    for b in range(2,i):
        x = to_base(i,b)
        if x.count('4')>best:
            best, base = x.count('4'),b
        if b**best>=i:
            break
    return f"{i} is the fouriest ({to_base(i,base)}) in base {base}"


def count_fours(n, base):
    fours = 0
    while n > 0:
        if n % base == 4:
            fours += 1
        n //= base
    return fours

def int_to_str_in_base(n, base):
    result = ""
    while n > 0:
        result = str(n % base) + result if n % base < 10 else "x" + result
        n //= base
    return result

def fouriest(i):
    highscore = 0
    winner = 5
    for base in range(5, i-3, 1):
        fours = count_fours(i, base)
        if fours > highscore:
            highscore = fours
            winner = base
        elif 4*base**(highscore) > i:
            break
    result = int_to_str_in_base(i, winner)
    return "{} is the fouriest ({}) in base {}".format(i, result, winner)

def fouriest(i):
    highscore = 0
    winner = 5
    for base in range(5, i-3, 1):
        fours = 0
        n = i
        while n > 0:
            if n % base == 4:
                fours += 1
            n //= base
        if fours > highscore:
            highscore = fours
            winner = base
        elif 4*base**(highscore) > i:
            break
    n = i
    result = ""
    while n > 0:
        result = str(n % winner) + result if n % winner < 10 else "x" + result
        n //= winner
    return "{} is the fouriest ({}) in base {}".format(i, result, winner)

def fouriest(numb):
    ans = ""
    temp = 0
    baz=0
    for i in range(5, 300):
        converted_string, modstring = "", ""
        currentnum = numb
        base = i
        while currentnum:
            mod = currentnum % base
            currentnum = currentnum // base
            converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
        if str(converted_string).count("4") > temp:
            temp = str(converted_string).count("4")
            ans = str(converted_string)
            baz = i
    ans = "".join([i if i.isdigit() else "x" for i in str(ans)])
    return "{} is the fouriest ({}) in base {}".format(numb, ans, baz)