"""Owned Huffman tree and independent optimal full-binary-tree cost on four symbols."""
import heapq,itertools,json
from functools import lru_cache

def build(freq):
    if not freq or any(type(v)is not int or v<=0 for v in freq.values()):raise ValueError('nonempty positive integer frequencies')
    serial=itertools.count();q=[];merges=[]
    for symbol,w in sorted(freq.items()):heapq.heappush(q,(w,next(serial),{'symbol':symbol}))
    while len(q)>1:
        wa,_,a=heapq.heappop(q);wb,_,b=heapq.heappop(q);node={'left':a,'right':b};heapq.heappush(q,(wa+wb,next(serial),node));merges.append({'two_smallest_weights':[wa,wb],'merged_weight':wa+wb})
    tree=q[0][2];codes={}
    def walk(node,prefix):
        if 'symbol'in node:codes[node['symbol']]=prefix or '0';return
        walk(node['left'],prefix+'0');walk(node['right'],prefix+'1')
    walk(tree,'');assert all(not codes[b].startswith(codes[a])for a in codes for b in codes if a!=b)
    return tree,codes,merges

def encode(message,codes):
    if any(s not in codes for s in message):raise ValueError('unknown symbol for this fixed codebook')
    return ''.join(codes[s]for s in message)

def decode(bits,tree):
    if any(b not in '01'for b in bits):raise ValueError('binary payload only')
    if 'symbol'in tree:
        if any(b!='0'for b in bits):raise ValueError('one-symbol contract uses zero')
        return tree['symbol']*len(bits)
    node=tree;out=[]
    for b in bits:
        node=node['left'if b=='0'else'right']
        if 'symbol'in node:out.append(node['symbol']);node=tree
    if node is not tree:raise ValueError('payload ends inside codeword')
    return ''.join(out)

def optimal_tree_cost(weights):
    n=len(weights)
    @lru_cache(None)
    def dp(mask):
        if mask&(mask-1)==0:return 0
        total=sum(w for i,w in enumerate(weights)if mask>>i&1);first=mask&-mask;candidates=[];sub=(mask-1)&mask
        while sub:
            if sub&first and sub!=mask:candidates.append(dp(sub)+dp(mask^sub))
            sub=(sub-1)&mask
        return total+min(candidates)
    return dp((1<<n)-1)

def demo():
    message='AAAAAAABBBCCD';freq={s:message.count(s)for s in sorted(set(message))};tree,codes,merges=build(freq);bits=encode(message,codes)
    weighted=sum(freq[s]*len(codes[s])for s in freq);oracle=optimal_tree_cost(list(freq.values()))
    assert codes=={'B':'00','D':'010','C':'011','A':'1'} and len(bits)==weighted==oracle==22 and decode(bits,tree)==message
    one,oc,_=build({'Z':4});assert oc=={'Z':'0'}and decode('0000',one)=='ZZZZ'
    invalid=[]
    for payload in ['01','012']:
        try:decode(payload,tree)
        except ValueError:invalid.append(True)
        else:raise AssertionError('invalid payload accepted')
    try:build({})
    except ValueError:empty_freq=True
    else:raise AssertionError('empty codebook input accepted')
    try:encode('X',codes)
    except ValueError:unknown=True
    else:raise AssertionError('unknown symbol accepted')
    assert encode('',codes)==decode('',tree)==''
    return {'authored_message':message,'frequencies':freq,'merge_log':merges,'tree':tree,'prefix_free_codes':codes,'payload_bits':bits,'payload_bit_count':len(bits),'weighted_path_length':weighted,'independent_all_binary_partitions_optimal_tree_cost':oracle,'fixed_two_bit_payload_count':2*len(message),'decoded':decode(bits,tree),'one_symbol_contract':{'codes':oc,'decoded':decode('0000',one)},'empty_frequency_input_rejected':empty_freq,'unknown_symbol_with_fixed_codebook_rejected':unknown,'empty_payload_with_known_codebook_roundtrip':True,'truncated_and_nonbinary_rejected':invalid,'header_dictionary_padding_and_file_bytes_not_counted':True,'actual_audio_or_product_compression':False}

if __name__=='__main__':print(json.dumps(demo(),indent=2))