<commit_before>#!/usr/bin/env python

import os
import re
from numpy import *
import copy

def read_words(max_length):
    words = open('words').read().lower().split()
    keep = []
    for word in words:
        if len(word)>max_length:
            break
        keep.append(word)
    return keep

def sort_word(word):
    return ''.join(sorted(word))

max_length = 5
dictionary = dict((sort_word(w),w) for w in read_words(max_length))
print 'word count =',len(dictionary)
for sw,w in tuple(dictionary.items()):
    for j in xrange(len(w)):
        swp = sw[j] + sw[:j] + sw[j+1:]
        dictionary[swp] = w
print 'expanded dictionary size =',len(dictionary)

def random_subset(s,n):
    r = ''
    for _ in xrange(n):
        i = random.randint(len(s))
        r += s[i]
        s = s[:i] + s[i+1:]
    return r

def subsets(s,n):
    """Return all substrings of size n."""
    if not n:
        yield ''
    else:
        n -= 1
        for i in xrange(len(s)-n):
            c = s[i]
            for sp in subsets(s[i+1:],n):
                yield c+sp

def subtract(a,b):
    for c in b:
        i = a.find(c)
        a = a[:i] + a[i+1:]
    return a

def random_word(letters):
    N = xrange(min(len(letters),max_length),1,-1)
    while 1:
        for n in N:
            for _ in xrange(100):
                s = sort_word(random_subset(letters,n))
                try:
                    return dictionary[s]
                except KeyError:
                    pass

directions = (array([1,0]),array([0,1]))

class Node(object):
    __slots__ = ['word','x','d','parent','children']

    def __init__(self,word,x,d,parent):
        self.word = word
        self.x = array(x)
        self.d = d
        self.parent = parent
        self.children = []

    def __deepcopy__(self,m):
        n = Node(self.word,self.x,self.d,self.parent)
        for c in self.children:
            n.children.append(copy.deepcopy(c,m))
        return n

    def _map(self,m):
        d = directions[self.d]
        for i in xrange(len(self.word)):
            m[tuple(self.x+i*d)] = self.word[i]
        for c in self.children:
            c._map(m)

    def map(self):
        m = {}
        self._map(m) 
        return m

    def mask(self):
        min = zeros(2,dtype=int)
        max = zeros(2,dtype=int)
        nodes = tuple(self.nodes())
        for n in nodes:
            min = minimum(min,n.x)
            max = maximum(max,n.x+(len(n.word)-1)*directions[n.d])
        min -= max_length+1
        max += max_length+1
        mask = zeros(max-min+1,dtype=bool)
        for n in nodes:
            d = directions[n.d]
            for j in xrange(len(n.word)):
                mask[tuple(n.x+j*d-min)] = True
        return min,mask

    def nodes(self):
        yield self
        for c in self.children:
            for n in c.nodes():
                yield n

    def signature(self):
        return (self.word,tuple(self.x),self.d,self.parent,tuple(c.signature() for c in self.children))

def print_tree(tree):
    m = tree.map()
    min = zeros(2,dtype=int)
    max = zeros(2,dtype=int)
    for x in m.iterkeys():
        min = minimum(min,x)
        max = maximum(max,x)
    table = zeros(max-min+1,dtype='|S1')
    table[:] = ' '
    for x,c in m.iteritems():
        table[tuple(x-min)] = c.upper()
    for r in xrange(len(table)):
        print '   ',' '.join(table[r])

def check_start(m,x,t):
    return not (tuple(x+t) in m or tuple(x-t) in m)

def check_space(m,x,t,word,k):
    s = 1-t
    for l in xrange(1,k+1):
        xp = x-l*t
        if tuple(xp-t) in m or tuple(xp-s) in m or tuple(xp+s) in m:
            return False
    for l in xrange(1,len(word)-k):
        xp = x+l*t
        if tuple(xp+t) in m or tuple(xp-s) in m or tuple(xp+s) in m:
            return False
    return True

def grow_tree(tree,letters):
    m = tree.map()
    nodes = tuple(tree.nodes())
    for n in xrange(min(len(letters),max_length-1),0,-1):
        for subset in subsets(letters,n):
            subset = sort_word(subset)
            for i,node in enumerate(nodes):
                s,t = directions[node.d],directions[1-node.d]
                for j in xrange(len(node.word)):
                    try:
                        word = dictionary[node.word[j]+subset]
                    except KeyError:
                        continue
                    x = node.x+j*s
                    if check_start(m,x,t):
                        for k in xrange(len(word)):
                            if word[k]==node.word[j] and check_space(m,x,t,word,k):
                                child = Node(word,x-k*t,1-node.d,k)
                                new_tree = copy.deepcopy(tree)
                                new_node = list(new_tree.nodes())[i]
                                new_node.children.append(child)
                                yield new_tree,subtract(letters,subset),word

def singly_pruned_trees(tree,letters):
    nodes = list(enumerate(tree.nodes()))
    nodes.sort(key=lambda n:len(n[1].word))
    for i,node in nodes:
        if not node.children:
            new_letters = letters + node.word 
            if node.parent>=0:
                new_tree = copy.deepcopy(tree) 
                new_nodes = list(new_tree.nodes())<commit_msg>Don't clobber anagrams in dictionary<commit_after>#!/usr/bin/env python

import os
import re
from numpy import *
import copy

def read_words(max_length):
    words = open('words').read().lower().split()
    keep = []
    for word in words:
        if len(word)>max_length:
            break
        keep.append(word)
    return keep

def sort_word(word):
    return ''.join(sorted(word))

# Build dictionary
max_length = 5
dictionary = {}
for w in read_words(max_length):
    sw = sort_word(w)
    dictionary[sw] = dictionary.get(sw,()) + (w,)
print 'sorted word count =',len(dictionary)
print 'word count =',sum(len(w) for w in dictionary.itervalues())
for sw,w in tuple(dictionary.items()):
    for j in xrange(len(sw)):
        swp = sw[j] + sw[:j] + sw[j+1:]
        dictionary[swp] = w
print 'expanded dictionary size =',len(dictionary)

def random_subset(s,n):
    r = ''
    for _ in xrange(n):
        i = random.randint(len(s))
        r += s[i]
        s = s[:i] + s[i+1:]
    return r

def subsets(s,n):
    """Return all substrings of size n."""
    if not n:
        yield ''
    else:
        n -= 1
        for i in xrange(len(s)-n):
            c = s[i]
            for sp in subsets(s[i+1:],n):
                yield c+sp

def subtract(a,b):
    for c in b:
        i = a.find(c)
        a = a[:i] + a[i+1:]
    return a

def random_word(letters):
    N = xrange(min(len(letters),max_length),1,-1)
    while 1:
        for n in N:
            for _ in xrange(100):
                s = sort_word(random_subset(letters,n))
                try:
                    words = dictionary[s]
                    return words[random.randint(len(words))]
                except KeyError:
                    pass

directions = (array([1,0]),array([0,1]))

class Node(object):
    __slots__ = ['word','x','d','parent','children']

    def __init__(self,word,x,d,parent):
        self.word = word
        self.x = array(x)
        self.d = d
        self.parent = parent
        self.children = []

    def __deepcopy__(self,m):
        n = Node(self.word,self.x,self.d,self.parent)
        for c in self.children:
            n.children.append(copy.deepcopy(c,m))
        return n

    def _map(self,m):
        d = directions[self.d]
        for i in xrange(len(self.word)):
            m[tuple(self.x+i*d)] = self.word[i]
        for c in self.children:
            c._map(m)

    def map(self):
        m = {}
        self._map(m) 
        return m

    def mask(self):
        min = zeros(2,dtype=int)
        max = zeros(2,dtype=int)
        nodes = tuple(self.nodes())
        for n in nodes:
            min = minimum(min,n.x)
            max = maximum(max,n.x+(len(n.word)-1)*directions[n.d])
        min -= max_length+1
        max += max_length+1
        mask = zeros(max-min+1,dtype=bool)
        for n in nodes:
            d = directions[n.d]
            for j in xrange(len(n.word)):
                mask[tuple(n.x+j*d-min)] = True
        return min,mask

    def nodes(self):
        yield self
        for c in self.children:
            for n in c.nodes():
                yield n

    def signature(self):
        return (self.word,tuple(self.x),self.d,self.parent,tuple(c.signature() for c in self.children))

def print_tree(tree):
    m = tree.map()
    min = zeros(2,dtype=int)
    max = zeros(2,dtype=int)
    for x in m.iterkeys():
        min = minimum(min,x)
        max = maximum(max,x)
    table = zeros(max-min+1,dtype='|S1')
    table[:] = ' '
    for x,c in m.iteritems():
        table[tuple(x-min)] = c.upper()
    for r in xrange(len(table)):
        print '   ',' '.join(table[r])

def measure_space(m,x,t):
    s = 1-absolute(t)
    space = 0
    xp = x.copy()
    while space<max_length:
        xp += t
        if tuple(xp+t) in m or tuple(xp-s) in m or tuple(xp+s) in m:
            break
        space += 1
    return space

def grow_tree(tree,letters):
    # Build list of start points
    m = tree.map()
    nodes = tuple(tree.nodes())
    starts = []
    for i,node in enumerate(nodes):
        s,t = directions[node.d],directions[1-node.d]
        for j in xrange(len(node.word)):
            c = node.word[j]
            x = node.x+j*s
            if tuple(x+t) not in m and tuple(x-t) not in m:
                before = measure_space(m,x,-t)
                after  = measure_space(m,x, t)
                if before or after:
                    starts.append((c,before,after,(i,x)))
    # Try all possible subsets everywhere
    for n in xrange(min(len(letters),max_length-1),0,-1):
        for subset in subsets(letters,n):
            subset = sort_word(subset)
            for c,before,after,ix in starts:
                for word in dictionary.get(c+subset,()):
                    for k in xrange(len(word)):
                        if word[k]==c and before>=k and after>=len(word)-1-k:
                            i,x = ix
                            new_tree = copy.deepcopy(tree)
                            node = list(new_tree.nodes())[i]
                            d = 1-node.d
                            node.children.append(Node(word,x-k*directions[d],d,k))
                            yield new_tree,subtract(letters,subset),word

def singly_pruned_trees(tree,letters):
    nodes = list(enumerate(tree.nodes()))
    nodes.sort(key=lambda n:len(n[1].word))
    for i,node in nodes:
        if not node.children:
            new_letters = letters + node.word 
            if node.parent>=0:
                new_tree = copy.deepcopy(tree) 
                new_nodes = list(new_tree.nodes())
{'fraction_non_alphanumeric': 0.13875023109632095, 'fraction_numerical': 0.006840451100018487, 'mean_word_length': 1.7726806765761147, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2159264', 'n_tokens_mistral': 3728, 'n_tokens_neox': 3596, 'n_words': 843}