title: Optimize the Scralphabet

text:
# Question
Title: Optimize the Scralphabet
# Scralphabet

A normal bag of Scrabble tiles contains the following letters (`?` is a blank tile, which can stand for any other letter):

```
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??

```

The letters have the following value:

```
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}

```

Given a normal bag of Scrabble tiles, construct the highest-scoring set of non-intersecting words (i.e., individual words, not on a Scrabble board) given the following conditions:

* The score for each word is `sum(letter_values) * length(word)`.
* You may only include a maximum of one word starting with each letter of the alphabet (so, a maximum of 26 words).
* Only valid Scrabble words (from this dictionary) may be included. You may read the dictionary from a file, hard-code it (ugh), or scrape it from the website.
* You need not use every tile, but all unused tiles form a single word, scored the same way, which subtracts from your score.

If you wish, your code may accept two inputs: the bag contents as a string, and the letter values in some format similar to a python `dict` (as above); alternatively, you can hard-code the bag contents and letter values. It should output the words in your set, their respective scores, and your total score, in some reasonable format.

Highest scoring set of words wins, with ties going to first posted.

# Answer
> 15 votes
# C, 2765 (optimal)

### Edit

Now all in a single C file. This just finds all the optimal solutions. They all must have 6 words of 15 letters and one 10-letter word consisting of 8 letters of value 1 and two blanks. For that I only need to load a fraction of the dictionary and I don't have to look for 15 letter words with blanks. The code is a simple exhaustive depth-first search.

```
#include <stdio.h>
#include <stdint.h>
#include <string.h>
struct w {
    struct lc { uint64_t hi,lo; } lc;
    char w[16];
} w15[6000], w10[40000];
int n15,n10;
struct lc pool = { 0x12122464612, 0x8624119232c4229 };
int pts[27] = {0,1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};
int f[27],fs[26], w15c[27],w15l[27][6000];
int count(struct lc a, int l) { return (l < 16 ? a.lo << 4 : a.hi) >> 4*(l&15) & 15; }
int matches_val(uint64_t a, uint64_t b) {
    uint64_t mask = 0x1111111111111111ll;
    return !((a - b ^ a ^ b) & mask);
}
int matches(struct lc all, struct lc a) { return matches_val(all.hi,a.hi) && matches_val(all.lo,a.lo); }
int picks[10];
void try(struct lc cur, int used, int level) {
    int c, i, must;
    if (level == 6) {
    for (i = 0; i<27; i++) if (count(cur, i) && pts[i]>1) return;
    for (i = 0; i < n10; i++) if(!(used & (1 << (w10[i].w[0] & 31))) && matches(w10[i].lc, cur)) {
        for (c = 0; c<level; c++) printf("%s ",w15[picks[c]].w);
        printf("%s\n",w10[i].w);
    }
    return;
    }
    for (i = 0; i < 26;i++) if (count(cur,fs[i])) break;
    must = fs[i];
    for (c = 0; c < w15c[must]; c++) { i = w15l[must][c]; if(!(used & (1 << (w15[i].w[0] & 31))) && matches(cur, w15[i].lc)) {
    struct lc b = { cur.hi - w15[i].lc.hi, cur.lo - w15[i].lc.lo };
    picks[level] = i;
    try(b, used + (1 << (w15[i].w[0] & 31)), level+1);
    }}
}
int cmpfs(int *a, int *b){return f[*a]-f[*b];}
void ins(struct w*w, char *s, int c) {
    int i;
    strcpy(w->w,s);
    for (;*s;s++)
    if (*s&16) w->lc.hi += 1ll << 4*(*s&15); else w->lc.lo += 1ll << 4*(*s&15) - 4;
    if (c) for (i = 0; i < 27;i++) if (count(w->lc,i)) f[i]++, w15l[i][w15c[i]++] = w-w15;
}
int main() {
    int i;
    char s[20];
    while(scanf("%s ",s)>0) {
    if (strlen(s) == 15) ins(w15 + n15++,s,1);
    if (strlen(s) == 10) ins(w10 + n10++,s,0);
    }
    for (i = 0; i < 26;i++) fs[i] = i+1;
    qsort(fs, 26, sizeof(int), cmpfs);
    try(pool, 0, 0);
}

```

Usage:

```
$time ./scrab <sowpods.txt
cc -O3    scrab.c   -o scrab
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS LAURUSTINE
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS LUXURIATED
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS LUXURIATES
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS ULTRAQUIET
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS UTRICULATE
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS LAURUSTINE
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS LUXURIATED
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS LUXURIATES
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS ULTRAQUIET
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS UTRICULATE
OVERADJUSTMENTS QUODLIBETARIANS ACKNOWLEDGEABLY WEATHERPROOFING EXEMPLIFICATIVE HYDROGENIZATION RUBIACEOUS
OVERADJUSTMENTS QUODLIBETARIANS WEATHERPROOFING ACKNOWLEDGEABLY EXEMPLIFICATIVE HYDROGENIZATION RUBIACEOUS

real    0m1.754s
user    0m1.753s
sys 0m0.000s

```

Note every solution is printed twice because when adding a 15-letter 'W' word 2 orders are created because there are 2 'W' tiles.

The first solution found with the point breakdown:

```
JUXTAPOSITIONAL 465
DEMISEMIQUAVERS 480
ACKNOWLEDGEABLY 465
WEATHERPROOFING 405
CONVEYORIZATION 480
FEATHERBEDDINGS 390
LAURUSTINE (LAURU?TI?E) 80
no tiles left

```

### Edit: explanation

What makes searching the entire space possible? While adding a new word I only take into account words that have the rarest remaining letter. This letter need to be in some word anyway (and a 15 letter word since this will be a non 1-value letter, though I don't check for that). So I start with words containing `J, Q, W, W, X, Z` which have counts around `50, 100, 100, 100, 200, 500`. At lower levels I get more cutoff because some words are eliminated by the lack of letters. Breadth of the search tree at each level:

```
0: 1
1: 49
2: 3046
3: 102560
4: 724040
5: 803959
6: 3469

```

Of course a lot of cutoff is gained by not checking non-optimal solutions (blanks in 15 letter words or shorter words). So it is lucky that 2765 solution can be achieved with this dictionary (but it was close, only 2 combinations of 15 letter words give a reasonable leftover). On the other hand it is easy to modify the code to find lower scoring combinations where not all the leftover 10 letters are 1-valued, though it would be harder to prove this would be an optimal solution.

Also the code shows classic case of premature optimization. This version of `matches` function makes the code only 30% slower:

```
int matches(struct lc all, struct lc a) {
    int i;
    for (i = 1; i < 27; i++) if (count(a, i) > count(all, i)) return 0;
    return 1;
}

```

I even figured out how to make the bit magic parallel comparison even shorter than in my original code (highest nibble cannot be used in this case, but this is not a problem, as I only need 26 out of 32 nibbles):

```
int matches_val(uint64_t a, uint64_t b) {
    uint64_t mask = 0x1111111111111111ll;
    return !((a - b ^ a ^ b) & mask);
}

```

But it gives zero advantage.

### Edit

Writing the explanation above I realized that most of the time is spent on scanning the list of words for those containing a specific letter not in the `matches` function. Calculating the lists upfront gave 10x speedup.

# Answer
> 6 votes
# Python 2, score: ~~1840~~ 2162

This program first finds the best scoring word available with the given tiles (without using wildcards), then makes 10000 attempts to include random words that meet the constraints of unique first character and having available tiles. With the current constants, the program takes 27 seconds to run on my machine. Using larger constants would probably find a higher scoring combination of words.

**UPDATE:** Now uses a 2 stage selection algorithm, so it finds the best of 50 words at each select stage. The penalty score is now used in the evaluation algorithm too.

```
from random import *

tilelist = ('AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMM'
        'NNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??')
maintiles = dict((t, tilelist.count(t)) for t in set(tilelist))
value = {"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,
        "J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,
        "S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
words = open('words.txt', 'rt').read().split()

def sumpoints(word):
    return len(word) * sum(value[c] for c in word)

ranked = sorted((sumpoints(w),w) for w in words)[::-1]
for points,word in ranked:
    if all(word.count(ch) <= maintiles[ch] for ch in word):
        firstword = word
        break

def findwordset(first):
    tiles = maintiles.copy()
    startletter = set(tilelist) - {'?'}
    startletter.discard(first[0])
    result = [ (first, sumpoints(first)) ]
    thistotal = sumpoints(first)
    for ch in first:
        tiles[ch] -= 1
    for i in range(30):
        best = None
        for word in sample(words, 50):
            if word[0] in startletter:
                if all(word.count(ch) <= tiles[ch] for ch in word):
                    points = sumpoints(word)
                    if best == None or points > best:
                        best, bestword = points, word
        if best:
            thistotal += best
            result.append( (bestword,best) )
            startletter.discard(bestword[0])
            for ch in bestword:
                tiles[ch] -= 1
    penaltyword = ''.join(c*n for c,n in tiles.items())
    penalty = sumpoints(penaltyword)
    return thistotal - penalty, result, tiles

best = None
for attempt in range(10000):
    wordset = findwordset(firstword)
    if best == None or wordset > best:
        best = wordset

total, result, tiles = best
penaltyword = ''.join(c*n for c,n in tiles.items())
penalty = sumpoints(penaltyword)
for word,points in result:
    print '%20s%6s' % (word, points)
print 'Remaining word "%s" penalty = %s' % (penaltyword, -penalty)
print 'Total score = %s' % total

```

I include here the best of a few runs:

```
$ python s.py
 OXYPHENBUTAZONE   615
   LIQUEFACTIONS   351
  DETERMINATIVES   280
   FAMILIARISERS   234
     JUNKETEERED   253
      WOODPIGEON   170
           GAYAL    45
         CLAUGHT    91
       BRIARWOOD   135
Remaining word "V??" penalty = -12
Total score = 2162

```

Note that I do not use the wild cards and pay a larger penalty (due to word length). A future enhancement may include wildcard use.

# Answer
> 6 votes
## Simulated annealing (score 2246)

```
180     ADDITIVELY
338     ERYTHROPHOBIA
345     FLAGELLOMANIACS
435     INTERSUBJECTIVE
171     KOWTOWERS
390     QUADRINGENARIES
250     WEAPONIZED
200     XENOGAMOUS
-9      for blank used as S
-9      for blank used as W
-18     FTU unused
Total score: 2246

```

Unfortunately this is non-deterministic. I'll try to fix that and find a deterministic seed which gives a better value.

```
import java.io.*;
import java.util.*;

public class PPCG50219 {
    // Plus two wildcards
    private static String CHAR_FREQ  = "9224<232911426821646422121";
    private static String CHAR_VALUE = "1332142418513113:11114484:";

    private static List<List<String>> WORDS;

    public static void main(String[] args) {
        init();

        Random rnd = new Random(1);
        FeasibleSolution initial = new FeasibleSolution();
        List<List<String>> shuffledByLetter = new ArrayList<List<String>>(WORDS);
        Collections.shuffle(shuffledByLetter,  rnd);
        for (List<String> list : shuffledByLetter) {
            Collections.shuffle(list, rnd);
            for (String word : list) {
                if (initial.canUse(word)) {
                    initial.use(word);
                    break;
                }
            }
        }

        FeasibleSolution best = anneal(initial, rnd);
        System.out.println(best.toStringDetailed());
    }

    private static void init() {
        try {
            WORDS = new ArrayList<List<String>>(26);
            for (int i = 0; i < 26; i++) WORDS.add(new ArrayList<String>());

            // Take dictionary from stdin with fallback to hard-coded path.
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1"));
            if (!br.ready()) {
                br.close();
                br = new BufferedReader(new InputStreamReader(new FileInputStream("/home/pjt33/notes/dict/sowpods"), "ISO-8859-1"));
            }

            String line;
            FeasibleSolution soln = new FeasibleSolution();
            while ((line = br.readLine()) != null) WORDS.get(line.charAt(0) - 'A').add(line);
            br.close();
        }
        catch (IOException ioe) {
            throw new RuntimeException(ioe);
        }
    }

    public static FeasibleSolution anneal(FeasibleSolution feasibleSolution, Random rnd)
    {
        //Random rnd = new Random();

        FeasibleSolution best = feasibleSolution;
        int bestScore = best.score();
        double temperature = bestScore / 10;

        FeasibleSolution current = best;
        int currentScore = bestScore;

        for (int i = 0; i < 1024; i++)
        {
            // Try out some random changes, and then adjust the temperature according to the results.
            FeasibleSolution bestAtT = current;
            for (int j = 0; j < 256; j++)
            {
                FeasibleSolution neighbour = current.randomNeighbour(rnd);
                int score = neighbour.score();

                // Use a simple threshold rather than a Boltzmann probability
                if (score >= currentScore - temperature)
                {
                    current = neighbour;
                    currentScore = score;
                    temperature *= 0.95;
                }
                if (score > bestScore)
                {
                    best = neighbour;
                    bestScore = score;
                }
            }

            if (current == bestAtT) temperature *= 1.01;
            if (temperature < 1E-6 * bestScore) break;
        }

        return best;
    }

    static class FeasibleSolution {
        private final String[] words;
        private int blanksUsed;
        private final int[] counts;

        private FeasibleSolution(String[] words) {
            this.words = words;

            counts = new int[26];
            for (String word : words) {
                if (word == null) continue;
                for (char ch : word.toCharArray()) counts[ch - 'A']++;
            }
            for (int i = 0; i < 26; i++) {
                int limit = CHAR_FREQ.charAt(i) - '0';
                if (counts[i] > limit) blanksUsed += counts[i] - limit;
            }
            if (blanksUsed > 2) throw new IllegalArgumentException("Required " + blanksUsed + " blanks");
        }

        public FeasibleSolution() {
            this(new String[26]);
        }

        public FeasibleSolution(FeasibleSolution copy) {
            this(copy.words.clone());
        }

        public boolean canUse(String word) {
            int offset = word.charAt(0) - 'A';

            String current = clear(offset);
            boolean rv = set(offset, word);

            clear(offset);
            if (!set(offset, current)) throw new IllegalStateException();

            return rv;
        }

        public void use(String word) {
            int offset = word.charAt(0) - 'A';
            clear(offset);
            if (!set(offset, word)) throw new IllegalArgumentException();
        }

        private boolean set(int offset, String word) {
            if (words[offset] != null) throw new IllegalStateException();

            if (word != null) {
                for (char ch : word.toCharArray()) {
                    int limit = CHAR_FREQ.charAt(ch - 'A') - '0';
                    counts[ch - 'A']++;
                    if (counts[ch - 'A'] > limit) blanksUsed++;
                }
            }

            words[offset] = word;
            return blanksUsed <= 2;
        }

        private String clear(int offset) {
            String word = words[offset];
            if (word != null) {
                for (char ch : word.toCharArray()) {
                    int limit = CHAR_FREQ.charAt(ch - 'A') - '0';
                    if (counts[ch - 'A'] > limit) blanksUsed--;
                    counts[ch - 'A']--;
                }
            }

            words[offset] = null;
            return word;
        }

        public int score() {
            int score = 0;

            List<List<Integer>> lengths = new ArrayList<List<Integer>>();
            for (int i = 0; i < 26; i++) lengths.add(new ArrayList<Integer>());
            int unused = 100;

            for (String word : words) {
                if (word == null) continue;
                for (char ch : word.toCharArray()) lengths.get(ch - 'A').add(word.length());
                unused -= word.length();
            }

            for (int i = 0; i < 26; i++) {
                int limit = CHAR_FREQ.charAt(i) - '0';
                int off = 0;
                List<Integer> l = lengths.get(i);
                if (l.size() > limit) {
                    off = l.size() - limit;
                    Collections.sort(l);
                }
                else if (l.size() < limit) {
                    int surplus = limit - l.size();
                    l.add(-surplus * unused);
                }
                for (; off < l.size(); off++) score += l.get(off) * (CHAR_VALUE.charAt(i) - '0');
            }
            return score;
        }

        public FeasibleSolution randomNeighbour(Random rnd) {
            FeasibleSolution soln = new FeasibleSolution(this);

            // Shake things up.
            List<Integer> used = new ArrayList<Integer>();
            int totalCount = 0;
            for (int i = 0; i < words.length; i++) {
                if (words[i] == null) continue;
                used.add(i);
                totalCount += words[i].length();
            }
            if (totalCount > 50) {
                int offset = used.get(rnd.nextInt(used.size()));
                soln.clear(offset);
            }

            // TODO We can probably get better results by biasing the shuffle.
            List<List<String>> shuffledByLetter = new ArrayList<List<String>>(WORDS);
            String theBitThatMatters = Arrays.toString(counts);
            Collections.shuffle(shuffledByLetter,  rnd);
            for (List<String> list : shuffledByLetter) {
                Collections.shuffle(list, rnd);
                for (String word : list) {
                    if (word.equals(soln.words[word.charAt(0) - 'A'])) continue;
                    if (soln.canUse(word)) {
                        soln.use(word);
                        if (!theBitThatMatters.equals(Arrays.toString(soln.counts))) return soln;
                    }
                }

                // To avoid getting trapped in a local oscillation.
                int off = list.get(0).charAt(0) - 'A';
                if (soln.words[off] != null) {
                    soln.clear(off);
                    return soln;
                }
            }

            throw new RuntimeException("This really shouldn't be reachable");
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (String word : words) {
                if (word == null) continue;
                if (sb.length() > 0) sb.append(", ");
                sb.append(word);
            }

            return sb.toString();
        }

        private static int wordScore(String word) {
            int wordScore = 0;
            for (char ch : word.toCharArray()) {
                if (ch != '?') wordScore += (CHAR_VALUE.charAt(ch - 'A') - '0');
            }
            return wordScore * word.length();
        }

        public String toStringDetailed() {
            int score = 0;

            List<List<Integer>> lengths = new ArrayList<List<Integer>>();
            for (int i = 0; i < 26; i++) lengths.add(new ArrayList<Integer>());
            int unused = 100;

            StringBuilder surplusChars = new StringBuilder();
            int unusedBlanks = 2;

            StringBuilder sb = new StringBuilder();
            for (String word : words) {
                if (word == null) continue;
                for (char ch : word.toCharArray()) lengths.get(ch - 'A').add(word.length());
                unused -= word.length();
                sb.append(wordScore(word)).append("\t").append(word).append("\n");
            }

            for (int i = 0; i < 26; i++) {
                int limit = CHAR_FREQ.charAt(i) - '0';
                int off = 0;
                List<Integer> l = lengths.get(i);
                if (l.size() > limit) {
                    off = l.size() - limit;
                    unusedBlanks -= off;
                    Collections.sort(l);
                }
                while (l.size() < limit) {
                    surplusChars.append((char)('A' + i));
                    l.add(-unused);
                }
                for (int j = 0; j < off; j++) sb.append(-l.get(j)).append("\tfor blank used as ").append((char)('A' + i)).append("\n");
                for (; off < l.size(); off++) score += l.get(off) * (CHAR_VALUE.charAt(i) - '0');
            }

            while (unusedBlanks > 0) {
                surplusChars.append('?');
                unusedBlanks--;
            }
            sb.append(-wordScore(surplusChars.toString())).append("\t").append(surplusChars).append(" unused\n");

            sb.append("Total score: ").append(score());
            return sb.toString();
        }
    }
}

```

# Answer
> 4 votes
# Python, score ~~2638~~ ~~2675~~ ~~2676~~ ~~2689~~ ~~2699~~ 2717

**Result:**

```
OXYPHENBUTAZONE for 615
MICROEARTHQUAKE for 525
FLAVOURDYNAMICS for 435
ADJUSTABILITIES for 375
PREINTERVIEWING for 360
WATERFLOODINGS for 308
EAGLE?OOD? for 100
Left-over word: E
2717

```

**Code:**

```
import time
from multiprocessing import Pool

start_tiles = "AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??"
start_tiles = {l: start_tiles.count(l) for l in set(start_tiles)}
values = {"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
with open("sowpods.txt") as f:
    full_dictionary = list(l.strip() for l in f if l.strip())

def num_wilds_needed(word, tiles):
    return sum(max(0, word.count(l) - tiles[l]) for l in word)

def word_is_possible(word, tiles):
    # never replace 1st letter with wild, for simplicity
    if tiles[word[0]] <= 0:
        return False

    return num_wilds_needed(word, tiles) <= tiles['?']

def word_score(word):
    return sum(values[c] for c in word) * len(word)

def final_score(words, tiles_left, print_leftover=False):
    left_over_word = ""
    for tile, counts in tiles_left.iteritems():
        left_over_word += tile * counts
    if print_leftover:
        print "Left-over word: %s" % (left_over_word,)
    return sum(word_score(word) for word in words) - word_score(left_over_word)

def filter_dictionary(dictionary, tiles_left, start_letters):
    return [word for word in dictionary
            if word[0] in start_letters and word_is_possible(word, tiles_left)]

def pick_word(next_word, start_letters, tiles_left, dictionary):
    if not word_is_possible(next_word, tiles_left):
        raise ValueError("Using word that is impossible: %s" % (next_word,))

    next_letters = set(start_letters)
    next_letters.remove(next_word[0])
    next_tiles = dict(tiles_left)
    for c in next_word:
        next_tiles[c] -= 1

    next_dictionary = filter_dictionary(dictionary, next_tiles, next_letters)

    return next_letters, next_tiles, next_dictionary

class FakeResult:
    def __init__(self, value):
        self.value = value
    def get(self, timeout=None):
        return self.value

class FakePool:
    def apply_async(self, f, args):
        res = f(*args)
        return FakeResult(res)

def proc_next_word(next_word,
                   start_letters, tiles_left, filtered_sorted_dictionary,
                   depth, picks, prefix):
    score = word_score(next_word)
    next_letters, next_tiles, next_dictionary = pick_word(
        next_word, start_letters, tiles_left, filtered_sorted_dictionary)

    if len(prefix) / 2 < 5:
        print "%sDepth %d: ?, %s for %d, %d possible words left" % (
            prefix, len(prefix) / 2, next_word, score, len(filtered_sorted_dictionary))

    next_words, next_score = search(FakePool(), next_letters, next_tiles, next_dictionary,
                                    depth-1, picks, prefix + "  ")

    if len(prefix) / 2 < 5:
        print "%sDepth %d: %d, %s for %d" % (
            prefix, len(prefix) / 2, score + next_score, next_word, score)

    return [next_word] + next_words, score + next_score

def wildify(word, tiles_left):
    # replace missing letters with wilds
    while True:
        for c in word:
            if tiles_left[c] < word.count(c):
                word = word[0] + word[1:].replace(c, '?',  word.count(c) - tiles_left[c])
                break
        else:
            break

    return word

def search(pool, start_letters, tiles_left, filtered_sorted_dictionary, depth, picks, prefix=""):
    if not filtered_sorted_dictionary:
        # no words left - penalize for tiles left
        return [], final_score([], tiles_left)

    if depth == 0:
        raise ValueError("Hit depth 0")

    if tiles_left['?'] > 0:
        # proc top few and re-calculate score based on wildcarding
        best_word_candidates = [wildify(w, tiles_left) for w in filtered_sorted_dictionary[:10000]]
        best_word_candidates.sort(key=word_score, reverse=True)
    else:
        # no wildification needed
        best_word_candidates = filtered_sorted_dictionary

    best_words = best_word_candidates[:picks]
    if depth == 1:
        # only look at 1 word since depth 0 will do nothing
        best_words = [best_words[0]]

    results = [pool.apply_async(proc_next_word, (next_word,
                                                 start_letters, tiles_left, filtered_sorted_dictionary,
                                                 depth, picks, prefix))
               for next_word in best_words]
    results = [result.get() for result in results]

    return max(results, key=lambda (words, result): result)

if __name__ == "__main__":
    start_letters = set("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
    tiles_left = dict(start_tiles)
    print "Preparing word list..."
    dictionary = filter_dictionary(full_dictionary, tiles_left, start_letters)
    dictionary.sort(key=word_score, reverse=True)
    print "Starting search..."
    pool = Pool(8)
    words, _ = search(pool, start_letters, tiles_left, dictionary, 666, 5)

    for word in words:
        for c in word:
            if tiles_left[c] <= 0:
                raise ValueError("Invalid word list")
            tiles_left[c] -= 1

    print
    print "\n".join(("%s for %s" % (word, word_score(word)) for word in words))
    print final_score(words, tiles_left, True)

```

**Explanation:**

Depth-first search which searches the entire tree, picking between the top `picks` best words at each stage.

I sort the entire word list once by score at the beginning. After picking each word, for the next iteration I filter out all the words that are now no longer possible, preserving the order, so I don't have to sort the list at each step. To deal with wildcards, if there's a possibility that a wild card is needed, I pick the top 10000 candidates, replace missing letters with wildcards if needed, and re-sort based on the new (lower) scores.

This output is for `picks=5` and took `8m01s` to run on my 8-core machine.

# Answer
> 3 votes
# Java 8, score ~~2641~~ 2681

The program starts by taking the 40 best words. For each word, it finds the 40 best words to go along. Of the 1600 combinations, the program takes the best 40. For each combination, the 40 best words are found, and the cycle repeats.

When just a few tiles are left, the remaining letters are combined with the two blanks for the final word.

## Update

I increased the threshold to the 50 best words. Also, each combination only adds words that are less than those already present. This prevents multiple permutations of the same group.

```
OXYPHENBUTAZONE: 615
MICROEARTHQUAKE: 525
INTERSUBJECTIVE: 435
DAFFADOWNDILLY: 406
PREINTERVIEWING: 360
AUTOALLOGAMIES: 238
GOODSIRES: 99
?A?: 3             (ZAX)
---
Total: 2681

```

The program:

```
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Scrabble {

    static final int[] scores = new int[]{1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3, 1, 1, 3, 10, 1, 1, 1, 1, 4, 4, 8, 4, 10, 0};
    static final int[] freqs = new int[]{9, 2, 2, 4, 12, 2, 3, 2, 9, 1, 1, 4, 2, 6, 8, 2, 1, 6, 4, 6, 4, 2, 2, 1, 2, 1, 2};

    static final int MAX = 50;

    public static void main(String[] args) throws IOException {
        List<String> words = Files.readAllLines(new File("C:/Users/Ypnypn/scrabble.txt").toPath());
        words.sort((s, t) -> score(t) - score(s));
        words.removeIf(w -> !works(w));

        List<List<String>> last = words.stream().map(Arrays::asList).collect(Collectors.toList()),
                finalList = new ArrayList();

        for (int i = 0; i < 10; i++) {
            List<List<String>> next = new ArrayList();
            for (int j = 0; j < MAX && j < last.size(); j++) {
                List<String> group = last.get(j);
                Object[] thirds = words.stream().filter(word -> workTogether(group, word) && least(word, group)).toArray();
                for (int k = 0; k < MAX && k < thirds.length; k++) {
                    List<String> newList = new ArrayList(group);
                    newList.add((String) thirds[k]);
                    next.add(newList);
                }
            }
            last = next;
            last.sort((s, t) -> t.stream().mapToInt(Scrabble::score).sum()
                                - s.stream().mapToInt(Scrabble::score).sum());
            for (List<String> l : last) {
                if (l.stream().mapToInt(String::length).sum() > 90) {
                    finalList.add(l);
                }
            }
        }
        finalList.forEach(g -> {
            List<Integer> chars = new ArrayList();
            int[] counts = new int[26];
            g.forEach(str -> str.chars().forEach(c -> counts[c - 'A']++));
            for (int i = 0; i < 26; i++) {
                while (counts[i] < freqs[i]) {
                    chars.add('A' + i);
                    counts[i]++;
                }
            }
            String end = words.stream()
                    .filter(w -> w.length() == chars.size() + 2)
                    .filter(w -> g.stream().noneMatch(s -> s.charAt(0) == w.charAt(0)))
                    .filter(w -> {
                        List<Integer> copy = new ArrayList(chars);
                        int _1 = 0, _2 = 0;
                        for (char c : w.toCharArray()) {
                            if (copy.contains((int) c)) {
                                copy.remove((Integer) (int) c);
                            } else if (_1 == 0) {
                                _1 = c;
                            } else if (_2 == 0) {
                                _2 = c;
                            } else {
                                return false;
                            }
                        }
                        return true;
                    }).findAny().orElse("");
            if (end.equals("")) {
                return;
            }
            char[] arr = end.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                if (chars.contains((int) arr[i])) {
                    chars.remove((Integer) (int) arr[i]);
                } else {
                    arr[i] = '?';
                }
            }
            g.add(new String(arr));
        });

        finalList.removeIf(g -> g.stream().mapToInt(String::length).sum() < 100);
        finalList.sort((s, t) -> t.stream().mapToInt(Scrabble::score).sum()
                                 - s.stream().mapToInt(Scrabble::score).sum());
        List<String> answer = finalList.get(0);
        for (String str : answer) {
            System.out.print(str + ": " + score(str));
            if (str.contains("?")) {
                String actual = words.stream().filter(s -> s.matches("^" + str.replace('?', '.') + "$")).findAny().get();
                System.out.print("             (" + actual + ")");
            }
            System.out.println();
        }
        System.out.println("---");
        System.out.println("Total: " + answer.stream().mapToInt(Scrabble::score).sum());
    }

    static boolean works(String str) {
        int[] counts = new int[26];
        for (char c : str.toCharArray()) {
            counts[c - 'A']++;
        }
        for (int i = 0; i < 26; i++) {
            if (counts[i] > freqs[i]) {
                return false;
            }
        }
        return true;
    }

    static boolean workTogether(List<String> strs, String str) {
        if (strs.stream().anyMatch(s -> s.charAt(0) == str.charAt(0))) {
            return false;
        }
        int[] counts = new int[26];
        strs.stream().forEach(s -> s.chars().forEach(c -> counts[c - 'A']++));
        str.chars().forEach(c -> counts[c - 'A']++);
        for (int i = 0; i < 26; i++) {
            if (counts[i] > freqs[i]) {
                return false;
            }
        }
        return true;
    }

    static boolean least(String str, List<String> strs) {
        int score = score(str);
        return strs.stream().allMatch(s -> score(s) >= score);
    }

    static int score(String word) {
        int score = 0;
        for (char c : word.toCharArray()) {
            if (c != '?') {
                score += scores[c - 'A'];
            }
        }
        return score * word.length();
    }
}

```

# Answer
> 2 votes
# Perl, score: 2655 ~~2630~~

```
#!perl -l
%p = qw{A 1 B 3 C 3 D 2 E 1 F 4 G 2 H 4 I 1 J 8 K 5 L 1 M 3 N 1 O 1 P 3 Q 10 R 1 S 1 T 1 U 1 V 4 W 4 X 8 Y 4 Z 10 x 0};
/[A-Z]+/,push @R,$& for <>;
@R = sort{length($b)<=>length($a)}@R;
for(@R) {push@W,$_;push@W,"$`x$'" while /./g;push@O,($_)x(1+length)}
$l = "AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZxx";
@S = map {$r='';for$x(A..Z,'x'){$r.="${x}{".(1*s/$x//g).",}"};"^$r\$"} map{"$_"}@W;
sub score{$r=0;$r+=$p{$_}for split'',$rr=pop;$r*length$rr}
@X = map{score$_}@W;
$f = 'x';
for(;;) {
$best = -1; $besti = 0;
for ($i=0;$i<@S;$i++) {
    next if $X[$i] < $best;
    if ($O[$i]!~/^[$f]/ && $l=~$S[$i]) {
    $best = $X[$i];
    $besti = $i;
    }
}
if($best < 0){
    $ls = score$l;
    print "left: $l (-$ls)";
    $tot -= $ls;
    print "total: $tot";
    exit;
}
$l=~s/$_// for $W[$besti]=~/./g;
$O[$besti]=~/./; $f .= $&;
print "$W[$besti]/$O[$besti] ($X[$besti])";
$tot += $X[$besti];
}

```

Use:

```
$ perl ./scrab.pl <~/sowpods.txt
OXYPHENBUTAZONE/OXYPHENBUTAZONE (615)
MICROEARTHQUAKE/MICROEARTHQUAKE (525)
NONOBJECTIVISMS/NONOBJECTIVISMS (465)
DAFFADOWNDILLY/DAFFADOWNDILLY (406)
PREINTERVIEWIxG/PREINTERVIEWING (345)
LITURGIOLOGxSTS/LITURGIOLOGISTS (240)
URDEE/URDEE (30)
EE/EE (4)
AA/AA (4)
left: AA (-4)
total: 2630

```

Use of blanks actually does not give that much while significantly slows down the execution:

```
$ perl ./scrab.pl <~/sowpods.txt
OXYPHENBUTAZONE/OXYPHENBUTAZONE (615)
MICROEARTHQUAKE/MICROEARTHQUAKE (525)
NONOBJECTIVISMS/NONOBJECTIVISMS (465)
DAFFADOWNDILLY/DAFFADOWNDILLY (406)
PREINTERVIEWED/PREINTERVIEWED (322)
LITURGIOLOGISTS/LITURGIOLOGISTS (255)
RUGAE/RUGAE (30)
EE/EE (4)
AA/AA (4)
left: Axx (-3)
total: 2623

```

After adding some heuristics:

```
$ time perl ./scrab.pl <~/sowpods.txt
OXYPHENBUTAZONE/OXYPHENBUTAZONE (615)
MICROEARTHQUAKE/MICROEARTHQUAKE (525)
NONOBJECTIVISMS/NONOBJECTIVISMS (465)
PREFIGURATIVELY/PREFIGURATIVELY (405)
DOWNREGULATIONS/DOWNREGULATIONS (300)
FORGEAxILITIES/FORGEABILITIES (238)
ADWAxDED/ADWARDED (104)
EA/EA (4)
left: L (-1)
total: 2655

real    3m58.517s
user    3m57.832s
sys 0m0.512s

```

# Answer
> 1 votes
# Python 3, score 2735

*(The optimal score of 2765, "6 words of 15 letters and one 10-letter word consisting of 8 letters of value 1 and two blanks" has been achieved by nutki.)*

I used a greedy approach similar to others':

I start with one-element lists containing the top scoring words containing Q's.

At every step for every list element I create `k = 800` new lists with the best legal words for the list. From the aggregated list of lists I keep the `k` top scoring lists and repeat the process 10 times.

Note that you can get the top `k` elements of an `n`-long list in O(n + k\*log n) which is O(n) if `k<<n` as in our case (`k = 800, n ~= 250000`) with a heap queue. I guess this method isn't used in other submission s hence the smaller `k` values.

I use wildcards along the way if needed for the words.

Runtime is a couple minutes for `k = 800`. Greater values and other optimizations haven't yielded better results yet.

Result:

```
DEMISEMIQUAVERS for 480
OXYPHENBUTAZONE for 615
ACKNOWLEDGEABLY for 465
FLASHFORWARDING for 435
INTERJACULATING for 375
COOPERATIVITIES for 330
METEOROID for 108
? is C for -45
? is M for -27
Left U for -1
Total score of 2735

```

I experimented with the Descartes product of the best words containing Q,J and X as these letter barely share words. My best score with this startegy was 2723 (`DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA`).

The unnecessary complicated spaghetti-code (with traces of experimentation with other methods):

```
import sys,heapq as hq

def score(s):
    r=0
    for c in s:
        r+=ord('1332142418513113:11114484:0'[ord(c)-65])-48
    return r*len(s)

def score_wl(rwl):
    ac=a[:]
    ssd=0
    for rwle in rwl:
        ac,sd=decr(ac,rwle)
        ssd+=sd
    return sum([score(rw) for rw in rwl])-ssd

def decr(av,nw):
    nav=av[:]
    scd=0
    for c in nw:
        if nav[ord(c)-65]>0:
            nav[ord(c)-65]-=1
        else:
            nav[ord('[')-65]-=1
            scd+=(ord('1332142418513113:11114484:'[ord(c)-65])-48)*len(nw)
    return (nav,scd)

def bestwordlist(w,ac,sw,count):
    stl=[swe[0] for swe in sw]
    sl=[]
    for we in w:
        if we[0] not in stl:
            acn,sd=decr(ac,we)
            if min(acn)>=0:
                sl+=[(we,score(we)-sd)]
    mw=hq.nlargest(count,sl,key=lambda p:p[1])
    res=[mwe[0] for mwe in mw]
    return res

def bestword(w,ac,sw):
    ms=0
    mw=''
    stl=[swe[0] for swe in sw]
    for we in w:
        if we[0] not in stl:
            acn,sd=decr(ac,we)
            if min(acn)>=0 and score(we)-sd>ms:
                ms=score(we)-sd
                mw=we
    return mw

def search(t,lev,av,sw):
    if lev>=len(t) and min(av)>=0:
        return [sw]
    if min(av)<0:
        return []
    r=[]
    stl=[swe[0] for swe in sw]
    if av[ord(tl[lev])-65]>0:
        for i in range(1,maxch):
            nw=t[lev][-i][0]
            if nw[0] not in stl:
                nav=decr(av,nw)[0]
                swn=sw[:]+[nw]
                r+=search(t,lev+1,nav,swn)
    else:
        r+=[sw]
    if len(r)<10000:
        return r
    else:
        return hq.nlargest(10000,r,key=score_wl)

args=sys.argv
maxch=300#int(args[1])
maxch2=800#int(args[2])

w=[]
with open('scr_words.txt','r') as f:
    for l in f:
        w+=[l[:-1]]

a=[ord(c)-48  for c in '9224<2329114268216464221212']
                       #ABCDEFGHIJKLMNOPQRSTUVWXYZ?

t=[]
tl='Q'
for c in tl:
    tp=[]
    wl=[(x,score_wl([x])) for x in w if c in x]
    wl=sorted(wl,key=lambda p:p[1])
    t+=[wl]

r=search(t,0,a,[])

rt=sorted(r,key=score_wl)[-maxch2:]

ms=0
res='-'

for i in range(10-len(tl)):
    rtn=[]
    for sw in rt:

        ac=a[:]
        for swe in sw:
            ac,sd=decr(ac,swe)

        bwl=bestwordlist(w,ac,sw,maxch2)

        if not bwl:
            rtn+=[sw]
        for bwle in bwl:
            rtn+=[sw+[bwle]]

    rt=sorted(rtn,key=score_wl)[-maxch2:]
    print(rt[-1],score_wl(rt[-1]),'- left')
    sys.stdout.flush()

ms=-1000000
for sw in rt:
    ssd=0
    ac=a[:]
    for swe in sw:
        ac,sd=decr(ac,swe)
        ssd+=sd
    sc=sum([score(swe) for swe in sw])-ssd
    left=''.join([chr(i+65)*v for i,v in enumerate(ac)])
    sc-=score(left)
    if sc>ms:
        ms=sc
        res=(sw,left)

fsw,left=res
print('\n\nres =',ms,' '.join(fsw),'left',left)
    v

```

---
Tags: code-challenge, string, optimization, scrabble
---


title: Generate a Pallette for an Image

text:
# Question
Title: Generate a Pallette for an Image
This is a successor to my previous Code Golf challenge, which may be found here.

This time, you are trying to determine what the contents of colors.txt should be.

Your task is to take from the input the path to an image and a number of colours, and write to colors.txt a list of that many colors chosen for that image.

Remember, you are generating pallettes to go with this challenge.

As usual, you are going for lowest score, but in this case, your score is given by `ceil(codeSize/(1+max(0,votes)))`, so upvotes will help you as well.

For **one or more** of the following images, you should test your generated pallettes (using one of the answers from this challenge to test them) and post the results for a variety of pallette sizes:

# Answer
# Java

796 bytes

```
import java.awt.Color;import java.awt.image.*;import java.io.*;import java.util.*;import javax.imageio.*;public class P{public static void main(String[] a) throws Exception{Random R=new Random();Scanner in=new Scanner(System.in);PrintStream o=new PrintStream("colors.txt");List<Color> col=new ArrayList<Color>();BufferedImage i=ImageIO.read(new File(in.nextLine()));int h=i.getHeight(),w=i.getWidth(),k=in.nextInt(),x,y,z=0,r,g,b;while(col.size()<k&&z<k*k){x=R.nextInt(w);y=R.nextInt(h);Color c=new Color(i.getRGB(x, y));r=5*(c.getRed()/5);g=5*(c.getGreen()/5);b=5*(c.getBlue()/5);c=new Color(r,g,b);if(!col.contains(c)){col.add(c);}z++;}while(col.size()<k)col.add(new Color(R.nextInt(256),+R.nextInt(256),R.nextInt(256)));for(Color c:col)o.println(c.getRed()+" "+c.getGreen()+" "+c.getBlue());}}

```

Picks random colors from the image, with each component rounded to the nearest multiple of 5, such that no color is selected twice. If, after n2 selections, it has not yet found n distinct colors, it picks the rest entirely at random.

**Some sample results:**

The black spaceship in 10 colors:

In 25 colors:

In 50 colors:

In 200 colors:

The gold spaceship in 10 colors:

In 25 colors:

In 50 colors:

In 200 colors:

And, finally, the exploding globe in 10 colors:

In 25 colors:

In 50 colors:

And in 200 colors:
> 1 votes

---
Tags: code-golf, popularity-contest, image-processing
---


title: Simple Tag Parser

text:
# Question
Title: Simple Tag Parser
This is a model of a forgiving HTML parser. Instead of parsing HTML and extracting attributes, in this code golf, the tag parser will be simple.

Write a function that parses a tag structure and returns its parenthized form. An opening tag consists of one lowercase letter, and a closing tag consists of one uppercase letter. For example, `aAbaAB` parses into `(a)(b(a))`, or in HTML, `<a></a><b><a></a></b>`. Of course, tags can be in juxtaposition and nest.

"Prematurely" closed tags must be handled. For example, in `abcA`, the `A` closes the outermost `a`, so it parses into `(a(b(c)))`.

Extra closing tags are simply ignored: `aAB` parses into `(a)`.

Overlapping tags are NOT handled. For example, `abAB` parses into `(a(b))`, not `(a(b))(b)`, by the previous rule of extra closing tags (`abAB` -\> `abA` (`(a(b))`) + `B` (extra)).

Assuming no whitespaces and other illegal characters in the input.

You are not allowed to use any library.

Here is a reference implementation and a list of test cases:

```
#!/usr/bin/python

def pars(inpu):
  outp = ""
  stac = []
  i = 0
  for x in inpu:
    lowr = x.lower()
    if x == lowr:
      stac.append(x)
      outp += "(" + x
      i = i + 1
    else:
      while len(stac) > 1 and stac[len(stac) - 1] != lowr:
        outp += ")"
        stac.pop()
        i = i - 1
      if len(stac) > 0:
        outp += ")"
        stac.pop()
        i = i - 1
  outp += ")" * i
  return outp

tests = [
  ("aAaAbB", "(a)(a)(b)"),
  ("abBcdDCA", "(a(b)(c(d)))"),
  ("bisSsIB", "(b(i(s)(s)))"),
  ("aAabc", "(a)(a(b(c)))"),
  ("abcdDA", "(a(b(c(d))))"),
  ("abcAaA", "(a(b(c)))(a)"),
  ("acAC", "(a(c))"),
  ("ABCDEFG", ""),
  ("AbcBCabA", "(b(c))(a(b))")
]

for case, expe in tests:
  actu = pars(case)
  print "%s: C: [%s] E: [%s] A: [%s]" % (["FAIL", "PASS"][expe == actu], case, expe, actu)

```

Shortest code wins.

# Answer
## Golfscript, 54 chars

```
{[]:|\{.96>{.|+:|;40\}{32+|?).')'*\|>:|;}if}%|,')'*}:$

```

Tests

```
;["aAaAbB" "abBcdDCA" "bisSsIB" "aAabc" "abcdDA" "abcAaA" "acAC" "aAB" "abAB" "AbcBCabA"]{.' '\$n}%

aAaAbBaAaAbB (a)(a)(b)
abBcdDCA (a(b)(c(d)))
bisSsIB (b(i(s)(s)))
aAabc (a)(a(b(c)))
abcdDA (a(b(c(d))))
abcAaA (a(b(c)))(a)
acAC (a(c))
aAB (a)
abAB (a(b))
AbcBCabA (b(c))(a(b))

```
> 1 votes

# Answer
## Haskell, 111 characters

```
s@(d:z)§c|c>'^'=toEnum(fromEnum c-32):s++'(':[c]|d<'='=s|d==c=z++")"|1<3=(z++")")§c
p=tail.foldl(§)"$".(++"$")

```

This one's pretty golf'd for Haskell. Fun feature: The stack and the accumulating output are kept in the same string!

Test cases:

```
> runTests
Pass: aAbaAB parsed correctly as (a)(b(a))
Pass: abcA parsed correctly as (a(b(c)))
Pass: aAB parsed correctly as (a)
Pass: abAB parsed correctly as (a(b))
Pass: aAaAbB parsed correctly as (a)(a)(b)
Pass: abBcdDCA parsed correctly as (a(b)(c(d)))
Pass: bisSsIB parsed correctly as (b(i(s)(s)))
Pass: aAabc parsed correctly as (a)(a(b(c)))
Pass: abcdDA parsed correctly as (a(b(c(d))))
Pass: abcAaA parsed correctly as (a(b(c)))(a)
Pass: acAC parsed correctly as (a(c))
Pass: AbcBCabA parsed correctly as (b(c))(a(b))

```

---

* Edit: (113 → 111) used an `@` pattern as suggested by FUZxxl
> 6 votes

# Answer
# Z80 Machine Code for TI-83+, 41 bytes

This is an implementation in hexadecimal machine code for a z80 cpu running on a TI-83+.

`11XXXX131AFE61380F6FE53E28CD9DB47DCD9DB4188EE1BDC03E29CD9DB4189BEF4504E5214CE1C9`

The XXXX (3 - 6 inclusive) is the 16-bit address of the string you are parsing, minus 1 byte.

Encoded in Z80-ASCII:

`¹XX≤¯•⟙8o↥>(ˣïÑ}ˣïÑ≠á↑γ∊>)ˣïÑ≠Ì⬆E↥!₄L↑Φ`

(Approximate, because TI calculators have their own character set.)

NOTE THAT THE `AsmPrgm` IS NOT INCLUDED IN THE ABOVE
> 5 votes

# Answer
## Windows PowerShell, 142 ~~146~~ ~~147~~ ~~152~~ ~~156~~ ~~169~~

```
{$s=''
-join([char[]]"$args "|%{if(90-ge$_){')'*(($x=$s.indexOf("$_".ToLower())+1)+$s.Length*!$x)
$s=$s.substring($x)}else{"($_"
$s="$_$s"}})}

```

Some things to note: This is just a script block. It can be assigned to a variable or given a function name, if necessary. You can also run it by putting `.` or `&` in front of it and the arguments at the end. Uses a final space to terminate unclosed tags.

Passes all tests. Test script:

```
$tests = ("aAaAbB","(a)(a)(b)"),("abBcdDCA","(a(b)(c(d)))"),("bisSsIB","(b(i(s)(s)))"),("aAabc","(a)(a(b(c)))"),("abcdDA","(a(b(c(d))))"),("abcAaA", "(a(b(c)))(a)"),("acAC","(a(c))")
"function f " + ((gc ./tags.ps1)-join"`n") | iex
$tests | %{
    $result = f $_[0]
    ("FAIL: $($_[0]):$($_[1]) - $result", 'PASS')[$result -ceq $_[1]]
}

```
> 2 votes

# Answer
# Python - 114 113 153 192 174 159 characters

```
from sys import *
s="";c=a=argv[1]
for f in a:
 o=c.find;p=f.lower
 if '@'<f<'\\':
\td=o(f)-o(p())
\ts+=")"*d
\tc=(c[:o(p())]+c[o(f)+1:])
 else:s+=("("+f)
print s

```

Abuses python's indentation parser to use one space for a full tab, five for two tabs.

**Edit 1** \- saved an unneeded space in the range() function

**Edit 2** \- fixed to deal with improper parse grammars, unterminated tags.

**Edit 3** \- fixed a bug whereby "incorrect" parses could be generated by ambiguity in the tag tree. Implemented a stack-based strategy, rather than a counter.

**Edit 4** \- renamed s.find to o to prevent save the chars used to repeatedly call it. did the same for f.lower.

**Edit 5** \- added the space/tab hack, saving three chars.

**Edit 6** \- ditched the loop in favor of ")"\*d.
> 2 votes

---
Tags: code-golf, string, parsing
---


title: Find the longest musical substring

text:
# Question
Title: Find the longest musical substring
A *musical string* is any string that can be played on a piano keyboard.

For those of us who weren't forced to learn the piano as kids, here is what the keyboard looks like.

So the string `feed a dead cabbage` is a musical string because every single letter corresponds to one of these nots.

Your challenge is to write a program that takes a string as input from STDIN, and finds the longest musical substring. Then your program must print the substring, and it's length. Here are some sample inputs/outputs.

> Input: "FEED ME! I'm hungry!"
>
> Output: feed 4

> Input: No no no, no musistrin!
>
> Ouput: 0

> Input: `"A **bad** !!!fAd82342"`
>
> Output: abadfad 7

> Input: "Good golfing!"
>
> Output: dg 2

# Rules

* Your output may be upper or lower-case, but there must be no punctuation or spaces.
* There will capitalization and punctuation in the input string, but this doesn't affect whether or not a substring is considered "musical" or not.
* There must be a space between the musical substring, and the number.

# Answer
# Pyth, ~~25~~ 23 bytes

```
pdJef!-T<G7+k.:@Grz0)lJ

```

2 bytes saved thanks to @Jakube.

Demonstration. Test harness.

Explanation:

* `rz0`: The input, in lowercase.
* `@Grz0`: Strip any non-alphabetic characters.
* `.:@Grz0)`: Generate all substrings.
* `+k.:@Grz0)`: Add in the empty string.
* `f ... +k.:@Grz0)`: Filter over these strings.
* `-T<G7`: Filter each string for non musical characters.
* `!-T<G7`: Negate the result. This is `True` if and only if the string was musical.
* `f!-T<G7+k.:@Grz0)`: Filter out the musical strings.
* `ef!-T<G7+k.:@Grz0)`: Take the last such string. `.:` orders substrings by size, so this is also the longest musical substring.
* `Jef!-T<G7+k.:@Grz0)`: Assign the result to `J`.
* `pdJ`: Print `J`, with `d`, space, as the ending character.
* `lJ`: Then, print the length of `J`.
> 4 votes

# Answer
# Ruby, ~~83~~ 75 characters

Fairly self-explanatory.

```
puts"#{s=gets.gsub(/[^a-z]/i,'').split(/[^a-g]/i).max_by &:size} #{s.size}"

```

Takes advantage of the fact that Ruby can split strings on regex (`.split(/[^a-g]/)`).
> 2 votes

# Answer
# Perl, 58

```
#!perl -p
$\=0;map{$i++;$\="$& $i"if/[a-g]{$i}/i}(s/\W//gr)x y!!!cd

```

Use:

```
$ perl ~/mus.pl <<<"FEED ME! I'm hungry!"
FEED 4

```

or

```
$ perl -pe'$\=0;map{$i++;$\="$& $i"if/[a-g]{$i}/i}(s/\W//gr)x y!!!cd' <<<"FEED ME! I'm hungry!"
FEED 4

```
> 1 votes

# Answer
# Java, 268

```
class Z{public static void main(String[]a){String s=new java.util.Scanner(System.in).nextLine().toLowerCase().replaceAll("[^a-z]",""),t;for(int i=s.length();i-->0;)if(!(t=s.replaceFirst("^(.*)([a-g]{"+i+"})(.*)$","$2")).equals(s)){System.out.println(t+" "+i);break;}}}

```

Expanded:

```
class Z {
    public static void main(String[] a) {
        String s = new java.util.Scanner(System.in).nextLine().toLowerCase().replaceAll("[^a-z]", ""), t;
        for (int i = s.length(); i-- > 0;) {
            if (!(t = s.replaceFirst("^(.*)([a-f]{" + i + "})(.*)$", "$2")).equals(s)) {
                System.out.println(t + " " + i);
                break;
            }
        }
    }
}

```
> 0 votes

# Answer
# R, ~~98~~ 94 bytes

```
p=strsplit(gsub("[^a-z]","",readline(),T),"[^a-gA-G]+")[[1]];m=max(n<-nchar(p));cat(p[n==m],m)

```

Ungolfed + explanation:

```
# Read from STDIN and remove all non-alphabetic characters
r <- gsub("[^a-z]", "", readline(), ignore.case = TRUE)

# Split r into a vector of substrings on characters other than a-g
p <- strsplit(r, "[^a-g]+")[[1]]

# Get the number of characters in each substring
n <- nchar(p)

# Get the length of the longest substring
m <- max(n)

# Print the string and length
cat(p[n == m], m)

```

Suggestions are welcome!

Note: The output is now mixed-case, which is allowed per the OP's edit. This saved 4 bytes.
> 0 votes

# Answer
# golflua, ~~84~~ ~~85~~ 84 bytes

```
B=I.r():g("%A",""):g("[^a-gA-G]"," ")M=0Q=""~@W B:gm("(%w+)")?#W>M M=#W Q=W$$w(Q,M)

```

I first ~~force lowercase, then~~ strip ~~spaces~~ non-letter characters, then remove all non-musical letters on the input (stdin). I then scan through each remaining word and compare its length before outputting the largest and length (stdout). There's probably a shorter way to do the loop, but at the moment this is what I've got.

An ungolfed Lua code would be

```
Line = io.read()                                  -- read stdin
NoSpaced = Line:gsub("%A","")                     -- strip non-letter chars
MusicalLetters = NoSpaced:gsub("[^a-gA-g]", " ")  -- remove non-musical letters
WordLen = 0, LongWord = ""                        -- helpers
for words in MusicalLetters:gmatch("(%w+)") do    -- scan for longest word
   if words:length() > WordLen then
      WordLen = words:length()
      LongWord = words
   end
end
print(LongWord, WordLen)                          -- output solution

```
> 0 votes

# Answer
## Perl 5 (106)

```
use List::Util reduce;$_=lc<>;s/[^a-z]//g;$_=reduce{length$a>length$b?$a:$b}m/[a-g]+/g;print"$_ ",0+length

```
> 0 votes

---
Tags: code-golf, string, music
---


title: CodeGolf - Barry the messy developer #2

text:
# Question
Title: CodeGolf - Barry the messy developer #2
> This is a follow-up of CodeGolf - Ignore the noise #1 the only problem being that Barry has made things even worse for us. Lets see what happened

### Update

I've added code to create random input and expected output because I'm not that good at explaining what I want, and I guess that sometimes words are more misleading than code (isn't that always?)

### Description

Another method in *Dumb Corp*'s API gives us the current price a provider is giving us for an item, the optimal price we would be making maximum sales with and the tendency of that price compared to previous prices as a string `UP` or `DOWN`. We need to decide if we should remove the item from the shop or wait.

### Input

```
80,90,UP
150,100,DOWN
65,65,UP
1618,1618,DOWN
840,1200,DOWN
54,12,UP
30,1,UP

```

For a huge input sample demo with expected output, put the following code (js) in your browsers console and it should output valid random input for testing.

```
var output = "";
var result = "";

for(i=10;i--;){
  var currentPrice = Math.floor(Math.random() * 10000) + 1;
  var optimalPrice = Math.floor(Math.random() * 10000) + 1;
  var tendency = Math.round(Math.random())?"UP":"DOWN";
  var tresult = "WAIT\n";

  if((currentPrice > optimalPrice && tendency == "UP") ||
     (currentPrice < optimalPrice && tendency == "DOWN")){
       tresult = "STOP\n";
     }

  output +=currentPrice+","+optimalPrice+","+tendency+"\n";
  result +=tresult;
}
console.log(output);
console.log(result);

```

As always we will have a variable `G` as our input, however if your language makes it easier for you to simply read the input, that's also fine. The format is constant, and follow the format `int,int,string`

### Desired Output

You're the brains of this operation, Barry should be doing this calculation on the server, but we can't count on him as you should know. You need to output `WAIT` if the tendency is towards the optimal price, or `STOP` if the tendency is towards loses.

In other words, with the `80,90,UP` as input, we know that there is a product with current price of 80 and optimal price of 90 with a tendency to rise up, so we should `WAIT`. On the other hand, `840,1200,DOWN` means the product price is going down and our optimal price is higher, so we should stop losses by outputting `STOP`.

If the two prices are identical, output `WAIT` regardless of the tendency.

Each product in a new line, single word per line:

```
WAIT
WAIT
WAIT
WAIT
STOP
STOP
STOP

```

Please, when possible, provide a way of verifying that your code is working since we can't all know just by looking at the syntax. As always, **use as few characters as possible** and remember that you're not competing against other languages necessarily, your competing against languages with similar syntax

# Answer
> 6 votes
# CJam, ~~31~~ ~~29~~ 27 characters

```
"㫅㍸ꕆ敟鸢Ꝓ約䢫솓儓隆뻨"2G#b128b:c~

```

This is just an encoded version of the following code (in order to make use of the scoring by characters):

```
r{',/:~3<)(f*~<"STOP""WAIT"?Nr}h

```

Run all test cases here.

There might be a way to shorten this by encoding `STOP` and `WAIT`, but I'm quite happy with the rest.

## Explanation

The code is surrounded by a loop which reads on line at a time, processes it, then pushes a newline, and reads the next line... The loop terminates once `r` returns an empty string (i.e. after all lines have been processed). That's this bit:

```
r{ ... Nr}h

```

As for processing each line, I'm making use of the fact that upper case letters are variables in CJam, so I can eval some of the input.

```
',/:~3<)(f*~<"STOP""WAIT"?
',/                        e# Split the input on commas.
   :~                      e# Eval each of the three resulting strings. The first two
                           e# will yield the prices, the third will dump a bunch of
                           e# values corresponding to the variables DNOPUW in the array.
     3<                    e# Truncate to three elements, so we only get the prices and
                           e# the values corresponding to U (0) and D (13).
       )(                  e# Slices off that variable value and decrement it, to get
                           e# something negative for UP and positive for DOWN.
         f*                e# Multiply both numbers by that value. So if we had UP then
                           e# both numbers will be negative now, otherwise they'll just
                           e# be scaled without affecting their relative size.
           ~<              e# Unwrap the array and check which element is larger.
             "STOP""WAIT"? e# Select the desired output string based on this boolean.

```

So the catch is that for `UP` we invert the relative sizes of the prices, so that we can cover all cases with a single inequality at the end.

# Answer
> 7 votes
# Perl, 35

```
#!perl -pl
/,/;$_=$`-$'&&$`>$'^/D/?STOP:WAIT

```

Test me.

# Answer
> 4 votes
# Perl, ~~77~~ 73 bytes

```
while(<>){@p=split",";print($p[0]<$p[1]and$p[2]=~/D/?"STOP":"WAIT")."\n"}

```

Here's how it works:

* `while(<>)` parses every line.
* `@p=split","` splits it by every comma. It's using the default Perl operator, `$_` (which is where the line is stored.)
* `print (ternary)` determines what to print.
* `$p[0]<$p[1]and$p[2]=~/D/` asks if the current price is less than the price we want, and it's going down (by checking for a D.)
* `(condition)?(if):(else)` is the ternary operator.
* If our condition earlier matched, it'll output `STOP`. Otherwise, it'll output `WAIT`.

I'm assuming there is no trailing newline on the input - a trailing newline produces an extra `WAIT`.

Thanks to Alex A. for helping me save 4 bytes!

# Answer
> 4 votes
# C, 85

```
c;main(i,j){for(;scanf("%d,%d,%c%*s",&i,&j,&c)>0;)puts(i-j&&i>j^c<70?"STOP":"WAIT");}

```

Test me.

# Answer
> 3 votes
**Ruby - 89 Chars**

```
G.split.map{|a|b,c,d=a.split(?,);puts (b.to_i>=c.to_i)^(e=d[2])&&(b!=c||e)?'STOP':'WAIT'}

```

RubyFiddle

With help from to bluetorange!

# Answer
> 3 votes
# Python 3, ~~89~~ ~~84~~ 82 bytes

```
for l in G:a,b,c=l.split(',');print('WSATIOTP'[a==b or(int(a)<int(b))^(c<'U')::2])

```

Explanation:

```
for l in G:                                   #For every line in G:
           a,b,c=l.split(',');                #Split the line into three strings.
                              print()         #Print the contained expression.

'WSATIOTP'                                    #'WAIT' and 'STOP' interleaved.
          [                              ::2] #Select every other character.
                or                            #If either expression is true, pick 'WAIT'
           a==b
                  (             )^(     )     #Select 'WAIT' if exactly one is true.
                   int(a)<int(b)              #If first number < second number.
                                   c<'U'      #If c is 'DOWN'

```

# Answer
> 3 votes
# R, ~~95~~ 108

R and strings, not really friends:)

```
eval(parse(t=sub("U","<",sub("D",">",gsub("(.*),(.*),(.).*","cat(if(\\1\\3=\\2)'WAIT\n'else'STOP\n')",G)))))

```

Input is the character vector `G` then changes each string into an `if` statement that is evaluated.

**Edit** Messed up my interpretation of the rules. Fix cost a few characters.

```
> G=c(
+     '80,90,UP',
+     '150,100,DOWN',
+     '65,65,UP',
+     '1618,1618,DOWN',
+     '840,1200,DOWN',
+     '54,12,UP',
+     '30,1,UP'
+ )
> eval(parse(t=sub("U","<",sub("D",">",gsub("(.*),(.*),(.).*","cat(if(\\1\\3=\\2)'WAIT\n'else'STOP\n')",G)))))
WAIT
WAIT
WAIT
WAIT
STOP
STOP
STOP
>

```

# Answer
> 2 votes
# Matlab, ~~100~~ 90 bytes

Not as small as I'd like - especially the conversion from boolean to the strings is very long. I tried to shave off a few bytes by switching to Octave, but apparently %c is not supported for textscan yet in Octave.

```
B=textscan(G,'%f,%f,%c%s\n');xor(B{1}>=B{2},B{3}==85);C(a)={'STOP'};C(~a)={'WAIT'};char(C)

```

Personally I think it is nice that this solution is the only one so far that does not use split :)

EDIT: originally solved the equals situation way too complex.

# Answer
> 2 votes
## Javascript ECMAScript 6, 112b

```
var O="";for(let E of G.split("\n"))[A,B,C]=E.split(","),O+=("U"<C||-1)*(A-B)>0?"STOP\n":"WAIT\n";console.log(O)

```

Only on ECMAScript 6 compatible browsers

### Explanation

```
("U"<C||-1)*(A-B)>0?"STOP\n":"WAIT\n"

```

It makes use of the fact that if we ask if 0 is true it will return false, so we can say 1 for `UP`, -1 for `DOWN`. Then we multiply that by the difference of current price and optimal price to make both of them work for the *greater than 0* part

If condition is met, return `STOP`, otherwise (including equal values) return `WAIT`

Needs further golfing

# Answer
> 2 votes
# C- 91 Bytes

Because C has to be there somewhere

Now looks very similar to @nutki version although working out whether to output "STOP" or "WAIT" is diffferent.

Ungolfed-

```
main(i,j)
{
    char c[5];
    while(scanf("%i,%i,%s",&i,&j,c)+1)
        puts((j-i)*(*c-70)<0?"STOP":"WAIT");
}

```

Golfed-

```
 main(i,j){char c[5];while(scanf("%i,%i,%s",&i,&j,c)+1)puts((j-i)*(*c-70)<0?"STOP":"WAIT");}

```

The old one

```
Ungolfed-

int main()
{
    int i,j;
    char *c="";
    while(scanf("%i,%i,%s",&i,&j,c)+1)
    {
        if(i<j)
        {
            if(*c-68)
                printf("WAIT\n");
            else
                printf("STOP\n");
        }
        if(i>j)
        {
            if(*c-68)
                printf("STOP\n");
            else
                printf("WAIT\n");
        }
        if(i==j)
            printf("WAIT\n");
    }
    return 0;
}

Golfed

#define W printf("WAIT\n");
#define S printf("STOP\n");
int main(){int i,j;char *c="";while(scanf("%i,%i,%s",&i,&j,c)+1){if(i<j){if(*c-68)W else S}if(i>j){if(*c-68)S else W}if(i==j)W}return 0;}

```

I'll continue to try to cut it down

# Answer
> 2 votes
# Javascript (*ES6*), 82 80 79 bytes

*Edit: -2 using @JuanCortés multiplication method*

*Edit: -1 using a trick to reduce the multiplication method*

```
alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>(c-o)*~{P:-2}[t]>0?'STOP':'WAIT'))

```

**Commented:**

```
alert(                           // alert final output after replacement
    G.replace(/(.+),(.+),(.)+/g, // capture group for sections of each line
                                 // (.)+ captures only the last character
                                 // . doesn't match newlines, so this runs for each line
        (x,c,o,t)=>              // use a function to calculate each replacement string
            (c - o)              // calculate difference, negative for o>c
            *                    // multiply by
            ~{ P: -2 }[t]        // { P: -2 }[t] returns -2 for UP ('P') -2, else undefined
                                 // ~-2 => 1, ~undefined => -1
            > 0                  // if result > 0 (muplication of negatives or positives)
            ? 'STOP' : 'WAIT'    // return corresponding replacement string
    )
)

```

**Snippet Demo:**

```
function run(){
    G = input.value;
    /* start solution */
    alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>(c-o)*~{P:-2}[t]>0?'STOP':'WAIT'))
    /* end solution */
}
```

```
<textarea id="input" cols="25" rows="7">80,90,UP
150,100,DOWN
65,65,UP
1618,1618,DOWN
840,1200,DOWN
54,12,UP
30,1,UP</textarea><br />
<button id="run" onclick="run();">Run</button>
```

**Revision History:**

```
// 80
alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>(c-o)*(t>'N'||-1)>0?'STOP':'WAIT'))

// 82
alert(G.replace(/(.+),(.+),(.)+/g,(x,c,o,t)=>+c>o&t>'N'|+c<o&t<'P'?'STOP':'WAIT'))

```

# Answer
> 1 votes
# Python 3 - ~~108~~ ~~106~~ ~~102~~ 97B

```
for l in G:a,b,c=l.split(',');s=int(a)-int(b);d=c<'E';print(['WAIT','STOP'][(s<0)*d+(s>0)*(1-d)])

```

Work in progress...

---
Tags: code-golf, string, number
---