def fibonacci(n):
    if n <= 1: return 1
    if n > 35: raise RuntimeError('Too large input')
    return fibonacci(n-1) + fibonacci(n-2)

using System;

namespace Solution {

  class FizzBuzz {
    public static string convert(int input){
    
      if (input % 3 == 0 && input % 5 == 0) {
        return "FizzBuzz";
      }
    
      if (input % 3 == 0) {
        return "Fizz";
      }
      
      if (input % 5 == 0) {
        return "Buzz";
      }
      
      return input.ToString();
    }
  }
}

#from __future__ import print_function

class AssertException(Exception):
    pass


'''Fix the dreaded Unicode Error Trap'''
_print = print
def print(*args, sep=' ', end='\n'):
    from io import StringIO
    def _escape(s): return s.encode('ascii', 'xmlcharrefreplace').decode('ascii')
    sio = StringIO()
    _print(*args, sep=sep, end=end, file=sio)
    _print(_escape(sio.getvalue()))
    sio.close()


def format_message(message):
    return message.replace("\n", "<:LF:>")


def expect(passed=None, message=None, allow_raise=False):
    if passed: print("\n<PASSED::>Test Passed")
    else:
        message = message or "Value is not what was expected"
        print("\n<FAILED::>{0}".format(message))
        if allow_raise: raise AssertException(message)


'''Fix the blocking asserts to non-blocking'''
def assert_equals(actual, expected, message=None, allow_raise=False):
    equals_msg = "{0} should equal {1}".format(repr(actual), repr(expected))
    if message is None: message = equals_msg
    else: message += ": " + equals_msg
    expect(actual == expected, message, allow_raise)


'''
Fix the blocking asserts to non-blocking
Also change the expected formula from `actual != expected` to `not (actual == expected)`
so that using this assertion can prevent the `==` / `!=` injection hack
'''
def assert_not_equals(actual, expected, message=None, allow_raise=False):
    equals_msg = "{0} should not equal {1}".format(repr(actual), repr(expected))
    if message is None: message = equals_msg
    else: message += ": " + equals_msg
    expect(not (actual == expected), message, allow_raise)


def expect_error(message, function):
    passed = False
    try: function()
    except: passed = True
    expect(passed, message)


'''Additional test functions: pass, fail, and assert_approx_equals'''
def pass_(): expect(True)
def fail(message): expect(False, message)


def assert_approx_equals(actual, expected, margin=1e-9, message=None, allow_raise=False):
    equals_msg = "{0} should be close to {1} with absolute or relative margin of {2}".format(
        repr(actual), repr(expected), repr(margin))
    if message is None: message = equals_msg
    else: message += ": " + equals_msg
    div = max(abs(actual), abs(expected), 1)
    expect(abs((actual - expected) / div) < margin, message, allow_raise)


def display(type, message, label="", mode=""):
    print("\n<{0}:{1}:{2}>{3}".format(type.upper(), mode.upper(), label, format_message(message)))


'''
Modern-Style Describe & It
Usage:
@describe('describe text')
def describe1():
    @it('it text')
    def it1():
        # some test cases...
'''
def _timed_block_factory(opening_text):
    from timeit import default_timer as timer
    from traceback import format_exception
    from sys import exc_info
    
    def _timed_block_decorator(s, before=None, after=None):
        print('<{}::>{}'.format(opening_text, s))
        def wrapper(func):
            if callable(before): before()
            time = timer()
            try: func()
            except:
                fail('Unexpected exception raised')
                tb_str = ''.join(format_exception(*exc_info())).replace('\n', '<:LF:>')
                print('<ERROR::>' + tb_str)
            print('<COMPLETEDIN::>{}'.format(round((timer() - time) * 1000, 2)))
            if callable(after): after()
        return wrapper
    return _timed_block_decorator

describe = _timed_block_factory('DESCRIBE')
it = _timed_block_factory('IT')


'''
Timeout utility
Usage:
with run_with_timeout(func, tuple_of_args, timeout_in_seconds) as run:
    Test.assert_equals(run.get(), expected_value)
Note: Timeout value can be a float.
'''
class run_with_timeout(object):
    def __init__(self, func, inputs, sec):
        from multiprocessing import Process, Queue
        def timeout_wrapper(func, inputs, q):
            q.put(func(*inputs))
        self.sec = sec
        self.q = Queue()
        self.p = Process(target=timeout_wrapper, args=(func, inputs, self.q))
        self.result = None
    def __enter__(self):
        self.p.start()
        return self
    def get(self):
        if self.result is None: self.result = self.q.get(timeout=self.sec)
        return self.result
    def __exit__(self, typ, val, traceback):
        self.q.close()
        self.p.terminate()
        self.p.join()
        if traceback: fail('Exceeded time limit of {:.3f} seconds'.format(self.sec))
        return True


'''Old-style Fixture'''
describe('Old-style Describe')
it('Old-style It')
assert_equals(0, 0)
assert_equals(0, 1)
print('<COMPLETEDIN::>')
it('Old-style It 2')
assert_equals('a', 'a')
assert_equals('a', 'b')
print('<COMPLETEDIN::>')
print('<COMPLETEDIN::>')


'''Sample Fixture #1'''
@describe('Sample Fixture #1')
def sample_describe_1():
    @it('Sample Testcase #1-1')
    def sample_it_1():
        assert_equals(0, 0)
        assert_equals(0, 1)
        assert_not_equals(0, 2)
        pass_()
        fail('This should fail')
    @it('Sample Testcase #1-2')
    def sample_it_2():
        expect_error('ZeroDivisionError', lambda: 0 / 0)
        assert_equals(0, 0 / 0)
        assert_equals(1, 1, 'This is not run due to exception')
    @it('Sample Testcase #1-3')
    def sample_it_3():
        assert_equals('abc', 'abc')
        # source code doesn't support utf-8 chars, but you can at least log and test unicode
        assert_equals('\uac00 \ub098 \ub2e4', '\uac00 \ub098 \ub2e4')
        print('\uac00 \ub098 \ub2e4')
        assert_equals('\uac00 \ub098 \ub2e4', 'a b c')


'''Sample Fixture #2: Featuring Before and After'''
@describe('Sample Fixture #2')
def sample_describe_2():
    a = {0}
    def before():
        a.add(len(a))
    @it('Sample Testcase #2-1', before=before, after=before)
    def sample_it_1():
        assert_equals(a, {0, 1})
    @it('Sample Testcase #2-2')
    def sample_it_2():
        assert_equals(a, {0, 1, 2})


'''Sample Fixture #3: Featuring Timeout'''
@describe('Sample Fixture #3')
def sample_describe_3():
    def wait_count(n):
        for _ in range(n): pass
        return n
    @it('Sample Testcase #3-1')
    def sample_it_1():
        with run_with_timeout(wait_count, (100,), 0.01) as run:
            assert_equals(run.get(), 100)
    @it('Sample Testcase #3-2')
    def sample_it_2():
        with run_with_timeout(wait_count, (10 ** 10,), 0.01) as run:
            assert_equals(run.get(), 10 ** 10)


'''Sample Fixture #4: Featuring assert_approx_equals'''
@describe('Sample Fixture #4')
def sample_describe_4():
    @it('Sample Testcase #4-1')
    def sample_it_1():
        assert_approx_equals(1, 1 + 1e-10, 1e-9)
        assert_approx_equals(1, 1 + 1e-7, 1e-9)
        assert_approx_equals(-1, -1 - 1e-10, 1e-9)
        assert_approx_equals(-1, -1 - 1e-7, 1e-9)
    @it('Sample Testcase #4-2')
    def sample_it_2():
        assert_approx_equals(0, 1e-10, 1e-9)
        assert_approx_equals(0, 1e-7, 1e-9)
        assert_approx_equals(0, -1e-10, 1e-9)
        assert_approx_equals(0, -1e-7, 1e-9)

public class Average {
   public static int averageFinder(int[] arr) {
      int total = 0;
      for(int num: arr){
         total += num;
      }
      int result = total / arr.length;
      return result;
   }
}

import java.util.*;

class Node {
  int value;
  Node left;
  Node right;
  
  public Node(int value) {
    this.value = value;
  }
}


class BST {
  public static boolean search(Node root, int key) {
    if(root == null) {
      return false;
    }
        
    while(root != null) {
      if(root.value == key) {
        return true;
      }
      
      if(root.value > key) {
        root = root.left;
      } else if(root.value < key) {
        root = root.right;
      }
    }
    
    return false;
  }
}

(ns fizzbuzz.core)

(defn divisible-by? [divisor number]
  (zero? (mod number divisor)))
  
(defn fizzbuzz [x]
  (map #(cond 
          (divisible-by? 15 %) "FizzBuzz"
          (divisible-by? 5 %) "Buzz"
          (divisible-by? 3 %) "Fizz"
          :else %)
        (range 1 (inc x))))

const flatten = arr =>
  arr.reduce((acc, item) => Array.isArray(item) ? [...acc, ...flatten(item)] : [...acc, item], []);

innerMatrix = array => array
  .slice(1, array.length - 1)
  .map(row => row.slice(1, array[0].length - 1));

"""
Created on Mon Oct 23 21:59:51 2017

BrainFuck tape, pointer & output vizualizer

@author: Blind4Basics - CodeWars
"""


# -----------------------------------------------------------------
#   Debugging commands usable in the BF code:
#
#       '?' char in the code to choose the debugging points.
#           You cnan name the check points with r'\w+' characters after the ?
#       '!' char to switch on/off the full debugging (print at the execution of each segment)
#
#
#   Other global switches available:
#
#        ALL:         vizualisation at each step of the code (each segment). Only when you're desperate...
#        DEACTIVATE:  force the deactivation of the vizualisation whatever is found in the code or the other switches are
#        CHAR_MODE:   if True, the tape will display ascii chars instead of numbers (Note: unprintable chars won't show up...)
#        LIMITER:     interrupt the executions after this number of printing. The count is reseted for each test
#
# -----------------------------------------------------------------


code = """                        # not working example
[
tape: _ S digits _ REF DEC S
]

>+                                 
>,
[?START                            
    >++++[<---------->-]<++        
    ?REMOVE_SOME
    [
      >++++[<++++++++++>-]<--      
      >>+<                         
    ]
    <[<]>[>]>                      
    ?ISNOTDOT
    [-<,>]<                        
]
>>,                                
?GET_DECIMAL
[                                  
    >++++[<-------->-]             
    +<<++++                        
    ?
    [->[->[>]]<<]                  
    ?MINUS4
    >[[-]<+>]                     
    ?LAST
]

<<<[<]>>[.>]
"""


#------------------------------------------------------------
#   Test cases:
#
#  'inputs' and corresponding 'expected' values
#    EOF char automatically added at the end of each input
#------------------------------------------------------------

inputs = ["3", "1.5", "101", "101.9", "101.2"]
exp =    ["3", "2",   "101", "102",   "101"]

""" GLOBAL SWITCHES """
ALL        = False
DEACTIVATE = False
CHAR_MODE  = False
LIMITER    = 50



import re

def brainFuckInterpreter(code, prog):
    
    def updateVizu(cmdSegment=''):
        
        def formatLst(lst, charMod=False):                          # Formater: align the cells of the tape and the list for the pointer
            formStr = "{: >" + str(max(map(len, map(str, data)), default=1)) + "}"
            return "[{}]".format(', '.join(formStr.format(chr(v) if charMod else v) for v in lst))
        
        if DEACTIVATE: return
        
        countDisplay[0] += 1                                        # Update the number of display already done (cf. LIMITER)
        
        vizu[-1][lastP[0]] = 0                                      # Erase the previous position of the pointer
        vizu[-1][p] = 1                                             # Place the pointer at the current position
        lastP[0] = p                                                # archive the current position of the pointer
        vizu[0] = c[0]                                              # archive the current command
        
        out = ''.join(output)
        cmd,tape,point = vizu
        print( "\n\n{}{}   tape\n{}   p\nout = '{}'".format(cmdSegment and cmdSegment+"\n",
                                                            formatLst(tape, CHAR_MODE),
                                                            formatLst(point), 
                                                            out) )
        if LIMITER >= 0 and LIMITER == countDisplay[0]: raise Exception("Too much printing: LIMITER = {}".format(LIMITER))
    
    
    def tapeLenUpdater():                                           # Make the tape length consistent with the actual position of the pointer (even if no value yet in the cells)
        if p >= len(data): 
            data.extend( [0] * (p-len(data)+1) )
            vizu[-1].extend( [0] * (len(data)-len(vizu[-1])) )
    
    
    def getNextInput():                                             # Simulate getting u'0000' when trying to get an input char after their exhaustion
        try:
            return ord(next(prog))
        except StopIteration:
            return 0
        
    
    p, lastP, i = 0, [0], 0                                         # p = pointer / lastP = previous P position (mutated) / i = segment of code index
    data = [0]                                                      # Tape initialization
    
    SWITCH, countDisplay = False, [0]                               # SWITCH: control for the "!" cmd swtich / countDisplay = control for LIMITER (as list to mutate it from a subroutine)
    output, vizu = [], ['', data, [0]]                              # vizu: [cmd, tape, pointer list]
    
    prog = iter(prog)
    code = re.findall(r'\++|<+|>+|-+|[,.[\]]|\?\w*|!', code)        # Make the executions more compact by using only segments of identical commands (=> '++++', '<<<', '[', '-', ']', check points with identifiers...)
    
    while 0 <= i < len(code):
        c = code[i]
        if False: print(c, data, p)                                 # activate manually. Only for debugging of the vizualiser itself...
        
        if   c[0] == '+': data[p] = (data[p] + len(c)) % 256
        elif c[0] == '-': data[p] = (data[p] - len(c)) % 256
        elif c[0] == '>': p += len(c) ; tapeLenUpdater()
        elif c[0] == '<': p -= len(c) ; tapeLenUpdater()
        elif c[0] == '.': output.append(chr(data[p]))
        elif c[0] == ',': data[p] = getNextInput()
        elif c[0] == '[':
            if not data[p]:
                depth = 1
                while depth > 0:
                    i += 1
                    c = code[i]
                    if c == '[': depth += 1
                    elif c== ']': depth -= 1
        elif c == ']':
            if data[p]:
                depth = 1
                while depth > 0:
                    i -= 1
                    c = code[i]
                    if c == ']': depth += 1
                    elif c == '[': depth -= 1
        
        
        # Vizualisation commands/executions 
        #--------------------
        elif c[0] == '?': updateVizu(c)                             # check point found
        
        if ALL or SWITCH and c[0] != "?": updateVizu(c)             # Vizualisation for swithes (avoid double printing for check points)
        
        if c[0] == '!': SWITCH = not SWITCH                         # Update '!' swtich state
        #--------------------
        
        i += 1
    return ''.join(output)


#--------------------
#  LAUNCH THE TESTS 
#--------------------

EOF = chr(0)
for p,e in zip(inputs,exp):
    print("Input: ", p)
    act = brainFuckInterpreter(code, p+EOF)
    
    print("Input: ", p)                        # remainder of the input
    print(act, " should be ", e)               # print actual/expected before assertion
    assert act == e
    
    print("SUCCESS\n---\n")

function test(str) {
  return (str.match(/\[([a-zA-Z]+)](.*)\[\/\1]/g)).join('');
}