#SKRZAT



Geek Challenge [SKRZAT] is an old, old game from Poland that uses a game console with two buttons plus a joy stick. As is true to its name, the game communicates in binary, so that one button represents a zero and the other a one. Even more true to its name, the game chooses to communicate so that the base of the number system is minus two, not plus two, so we'll call this representation "Weird Binary". Thus the bit positions label the powers of minus two, as seen in the following five-bit tables:

    | ------------------------------------------------------------------------- |
    |  Bits  |  Value  |  Bits  |  Value  |  Bits  |  Value  |  Bits  |  Value  |
    | ------ | ------- | ------ | ------- | ------ | ------- | ------ | ------- |
    | 00000  |    0    | 01000  |    -8   | 10000  |    16   | 11000  |    8    |
    | 00001  |    1    | 01001  |    -7   | 10001  |    17   | 11001  |    9    |
    | 00010  |   -2    | 01010  |   -10   | 10010  |    14   | 11010  |    6    |
    | 00011  |   -1    | 01011  |    -9   | 10011  |    15   | 11011  |    7    |
    | 00100  |    4    | 01100  |    -4   | 10100  |    20   | 11100  |    12   |
    | 00101  |    5    | 01101  |    -3   | 10101  |    21   | 11101  |    13   |
    | 00110  |    2    | 01110  |    -6   | 10110  |    18   | 11110  |    10   |
    | 00111  |    3    | 01111  |    -5   | 10111  |    19   | 11111  |    11   |
    | ------------------------------------------------------------------------- |

    | ------------------------------------------------------------------------- |
    |  Bits  |  Value  |  Bits  |  Value  |  Bits  |  Value  |  Bits  |  Value  |
    | ------ | ------- | ------ | ------- | ------ | ------- | ------ | ------- |
    | 01010  |   -10   | 00010  |    -2   | 11010  |    6    | 10010  |    14   |
    | 01011  |    -9   | 00011  |    -1   | 11011  |    7    | 10011  |    15   |
    | 01000  |    -8   | 00000  |    0    | 11000  |    8    | 10000  |    16   |
    | 01001  |    -7   | 00001  |    1    | 11001  |    9    | 10001  |    17   |
    | 01110  |    -6   | 00110  |    2    | 11110  |    10   | 10110  |    18   |
    | 01111  |    -5   | 00111  |    3    | 11111  |    11   | 10111  |    19   |
    | 01100  |    -4   | 00100  |    4    | 11100  |    12   | 10100  |    20   |
    | 01101  |    -3   | 00101  |    5    | 11101  |    13   | 10101  |    21   |
    | ------------------------------------------------------------------------- |

Numbers are presented on the screen in Weird Binary, and then numbers are accepted in response from the console as a stream of zeroes and ones, terminated by a five-second pause.  You are writing a computer program to support the novice geek in playing the game by translating numbers between decimal and Weird Binary.

#Input

The `skrzat` function will either convert into Weird Binary or out of Weird Binary: The first parameter will be either the letter `"b"`, which indicates that the second parameter is written in Weird Binary and needs to be converted to decimal; the letter `"d"` indicates that the second parameter is a decimal and needs to be converted to Weird Binary.  The second parameter will be in the range to fit within a 15-bit Weird Binary number, which represents the decimal number range -10922 to 21845, inclusive.

#Output

For each conversion problem, return the type of problem, its input string, and the converted result in the format shown below, replicating even the spacing exactly as shown. Leading zeroes are not allowed.

return format: `'From {binary || decimal}: {non-converted value} is {converted value}'`

#Sample Input

    skrzat('b', '1001101')
    skrzat('b', '0111111')
    skrzat('b', '101001000100001')
    skrzat('b', '010010001000010')
    skrzat('b', '100110100110100')
    skrzat('d', -137)
    skrzat('d', 137)
    skrzat('d', 8191)
    skrzat('d', -10000)
    skrzat('d', 21000)

#Sample Output

    'From binary: 1001101 is 61'
    'From binary: 0111111 is -21'
    'From binary: 101001000100001 is 19937'
    'From binary: 010010001000010 is -7106'
    'From binary: 100110100110100 is 15604'
    'From decimal: -137 is 10001011'
    'From decimal: 137 is 110011001'
    'From decimal: 8191 is 110000000000011'
    'From decimal: -10000 is 10100100110000'
    'From decimal: 21000 is 101011000011000'

Difficulty: interview

Starter code:

def skrzat(base, number):
	

Solutions:
def b(n):
    if not n: return '0'
    r = []
    while n:
        r.append(n % 2)
        n = (n - n % 2) / -2
    return ''.join(str(c) for c in r[::-1])

def d(n):
    r = 0
    for c in n: r = -2 * r + int(c)
    return r

def skrzat(base, n):
    if base == 'b': return 'From binary: %s is %d' % (n, d(n))
    if base == 'd': return 'From decimal: %d is %s' % (n, b(n))
    raise ValueError('unknown base')

from math import log
from math import ceil

def skrzat(base, number):
    
    if base == 'b':
        return 'From binary: ' + number + ' is ' + str(toDecimal(number))
    
    if base == 'd':
        return 'From decimal: ' + str(number) + ' is ' + toWBinary(number)
    
def toDecimal(number):
    if len(number) == 1:
        return int(number)    
    # e.g  (A) 1    -> 1    
    # e.g  (B) 10   -> ( (1) * (-2) + 0 )
    # e.g  (C) 101  -> ( (1) * (-2) + 0 ) * (-2) + 1 = B * (-2) + 1
    # e.g  (D) 1010 -> C * (-2) + 0
    # ...
    return toDecimal(number[:-1]) * (-2) + int(number[-1])
    
# posCurrentOne is the position (0 is position of the right digit) of 
# the last 1 knew (left to right)
# at the begining we don't know this position so we arbitrarily initialize
# this to -1. It is useful for insert the zerros after
def toWBinary(number, posCurrentOne = int(-1)):
    s = ''
            
    if not(number) :
        if posCurrentOne == -1:
            return '0'
        # if we know the last 1 is in position 2, and the number is egal to 0,
        # then we can complete with 2 zerros after and return the result  
        s += '0' * posCurrentOne
        return s    
    
    # We begin by calculate the number of digit necessary
    # if number is egal to  1 we need 1 digits
    # if number is egal to  2 we need 3 digits
    # if number is egal to -1 we need 2 digits
    # ...
    
    # if the number is > 0, we need odd  digits
    # if the number is < 0, we need even digits
    
    # if number is > 0, if the number of digits usefull is N, then the greatest
    # number possible is :
    
    # (-2 ** 0)                         = 1 for 1 digit
    # (-2 ** 0) + (-2 ** 2)             = 5 for 3 digits
    # (-2 ** 0) + (-2 ** 2) + (-2 ** 4) = 21 for 4 digits
    
    # so with S the max number with N digits we have:
    # S = sum(i=1,(N+1)/2) [(-2) ** (2 * (i - 1))]
    # it is egal to
    # S = sum(i=0,(N-1)/2) [4 ** i]
    # so 
    # S  = 1 + 4 + ... + 4 ** ((N-1)/2)
    # in multiply per 4
    # 4S =     4 + ... + 4 ** ((N-1)/2) + 4 ** ((N+1)/2)
    # with substraction
    # 4S - S = 4 ** ((N+1)/2) - 1
    # S = (4 ** ((N+1)/2) - 1) / 3
    
    # with x the decimal number to convert,
    # whe surch N so that 
    # S >= x
    
    # 4 ** ((N+1)/2) - 1 / 3 >= x
    # 4 ** ((N+1)/2)         >= 3x + 1
    
    # we use the log
    # ((N+1) / 2) log(4)     >= log(3x + 1)
    
    # but log(4) = log(2*2) = 2log(2) so
    # (N+1) log(2)           >= log(3x + 1)
    #                      N >= (log(3x + 1) / log(2)) - 1
    #
    # and we must have N integer and odd
    # so we use ceil and if the result is even we add 1
    # we have also N the number of digit necessary. And so we know
    # the digit in position N-1 is egal to 1
    
    if number > 0 :
        N = int( ceil(log( 3  *number +1, 2)) - 1)
        if not(N % 2) :
            N += 1    
            
    # by the same way we calculate N if number is > 0 
    else :
        N = int( ceil(log((-3)*number + 2, 2)) - 1)
        if (N % 2) :
            N += 1

    # if the last one calculate is in position 2 and we need 1 digit
    # we insert 2 - 1 = 1 zerro and one 1
    s += '0' * (posCurrentOne - N)
    s += '1'
        
    # if we have N digits, the digit in position N-1 is to one 
    # and correspond to (-2) ** (N-1). So we can substract this value
    # and iterate. We indicate so the position N -1
    
    return s + toWBinary(number - ((-2) ** (N-1)), N - 1 )

toDex = lambda n: int(n[-1]) - 2*toDex(n[:-1]) if n else 0
toBin = lambda n: toBin((n-n%2)/-2) + str(n%2) if n else ''
    
def skrzat(base, number):
    if not number: return 'From decimal: 0 is 0'
    elif base in 'b': return 'From binary: %s is %d'%(number, toDex(number))
    elif base in 'd': return 'From decimal: %d is %s'%(number, toBin(number))

def skrzat(t, i):
    return "From binary: "+str(i)+" is "+str((2863311530^int(i,2))-2863311530) if t=='b' else "From decimal: "+str(i)+" is "+str(bin((2863311530+i)^2863311530))[2:]

import math


def convert_to_base(a, b):
    if a == 0:
        return 0

    remainders = []

    while a != 0:
        c = a / b
        if c < 1:
            c = math.ceil(c)
        else:
            c = math.floor(c)

        d = a - b*c
        while d < 0:
            c += 1
            d = a - b*c

        a = c
        remainders.append(str(int(d)))

    remainders.reverse()
    return int("".join(remainders))


def skrzat(base, number):
    if base == 'b':  # b->d
        bits = reversed([int(bit) for bit in number])
        dec = 0
        for power, bit in enumerate(bits):
            dec += bit * ((-2)**power)

        return "From binary: {0} is {1}".format(number, dec)
    else:  # d->b
        binary = convert_to_base(number, -2)
        return "From decimal: {0} is {1}".format(number, binary)

def skrzat(base, n):
    if base == "b" : return 'From binary: {} is {}'.format(n,sum([int(j)*((-2)**i)for i,j in enumerate(n[::-1])]))  
    else:
        def do(n1):
            li = []
            while n1 != 0:
                li.append(str(abs(n1 % (-2)))) ; n1 //= -2
            return li[::-1]
        return 'From decimal: {} is {}'.format(n,"".join([do(abs(n)),do(-n)][n>0]) or 0)

def skrzat(base, number):
    convertor = { "b": {"name": "binary", "func": from_weird_binary},
          "d": {"name": "decimal", "func": to_weird_binary} }
    return "From {}: {} is {}".format(convertor[base]["name"], number, convertor[base]["func"](number))

def to_weird_binary(number):
    res = ""
    while number:
        number, x = divmod(number, -2)
        if x < 0:
            number += 1
        res += str(abs(x))
    return res[::-1] or "0"

def from_weird_binary(number):
    return sum([int(d) * (-2) ** i for i, d in enumerate(reversed(number))])

def skrzat(base, number):
    s = 0xAAAAAAAA

    if base == 'b':
        i = int(number, 2)
        return f"From binary: {number} is {(s ^ i) - s}"
    elif base == 'd':    
        return f"From decimal: {number} is {(number + s) ^ s:b}"

def skrzat(base, number):
    def to_binary(number):
        schroeppel2 = 0xAAAAAAAA
        return "From decimal: {} is {}".format(number, bin((int(number) + schroeppel2) ^ schroeppel2)[2:])
    def to_decimal(number):
        return "From binary: {} is {}".format(number, sum(int(d)*(-2)**i for i, d in enumerate(reversed(number))))

    if base == "b":
        return to_decimal(number)
    return to_binary(number)

def to_dec(binary):
    sum = 0
    binary = binary[::-1]
    for index, bit in enumerate(binary):
        sum += int(bit) and (-2)**index or 0
    return sum

def test_to_dec():
    assert to_dec("00000") == 0
    assert to_dec("00001") == 1
    assert to_dec("00010") == -2
    assert to_dec("00011") == -1
    assert to_dec("00100") == 4
    assert to_dec("00101") == 5
    assert to_dec("00110") == 2
    assert to_dec("00111") == 3
    assert to_dec("01000") == -8
    assert to_dec("01001") == -7
    assert to_dec("01010") == -10
    assert to_dec("10000") == 16
    assert to_dec("10001") == 17
    assert to_dec("10010") == 14
    assert to_dec("11000") == 8
    assert to_dec("11001") == 9
    assert to_dec("11010") == 6
    assert to_dec("1001101") == 61
    assert to_dec("0111111") == -21

BINARIES = dict(
    [(to_dec(binary[2:]), binary[2:]) 
      for binary in map(bin, range(2**15))
      ])

def to_binary(decimal):
    return BINARIES[int(decimal)]

def test_to_binary():
    assert to_binary(to_dec("00000")) == "0"        # 0
    assert to_binary(to_dec("00001")) == "1"        # 1
    assert to_binary(to_dec("00010")) == "10"       # -2
    assert to_binary(to_dec("00011")) == "11"       # -1
    assert to_binary(to_dec("00100")) == "100"  # 4
    assert to_binary(to_dec("00101")) == "101"  # 5
    assert to_binary(to_dec("00110")) == "110"  # 2
    assert to_binary(to_dec("00111")) == "111"  # 3
    assert to_binary(to_dec("01000")) == "1000" # -8
    assert to_binary(to_dec("01001")) == "1001" # -7
    assert to_binary(to_dec("01010")) == "1010" # -10
    assert to_binary(to_dec("10000")) == "10000"
    assert to_binary(to_dec("10001")) == "10001"
    assert to_binary(to_dec("10010")) == "10010"
    assert to_binary(to_dec("11000")) == "11000"
    assert to_binary(to_dec("11001")) == "11001"
    assert to_binary(to_dec("11010")) == "11010"
    assert to_binary(to_dec("1001101")) == "1001101"
    assert to_binary(to_dec("0111111")) == "111111"

def skrzat(base, number):
    basename = base == 'b' and 'binary' or 'decimal'
    result = base == 'b' and to_dec(number) or to_binary(number)
    return 'From {0}: {1} is {2}'.format(basename, number, result)

def test_skrzat():
    assert skrzat('b', '10001011') == 'From binary: 10001011 is -137'
    assert skrzat('b', '110011001') == 'From binary: 110011001 is 137'
    assert skrzat('b', '1001101') == 'From binary: 1001101 is 61'
    assert skrzat('b', '0111111') == 'From binary: 0111111 is -21'
    assert skrzat('d', 0) == 'From decimal: 0 is 0'
    assert skrzat('d', -137) == 'From decimal: -137 is 10001011'
    assert skrzat('d', 137) == 'From decimal: 137 is 110011001'