title: Hello Shue! (Cops)

text:
# Question
Title: Hello Shue! (Cops)
Robbers thread

In this challenge, your task is to write a program `h` that outputs "Hello Shue!". Next, you have to choose a string `i` and also write a Shue program `p`, so that `p(i)=h`. Your score is `len(p)+len(i)`. Your answer will contain the language of `h`, `i` and your score (please write the score as `len(p)+len(i)=score`). Robbers will try to find `p`. Note that any working `p`, that is as long as your `p` or shorter means that your answer is defeated, even if it wasn't the solution you intended. The undefeated cop answer with the smallest score wins (per language).

To understand this challenge let's look at an example submission in Python:

> Python 3, score 47+22=69
>
> `(rint?KH++lloooShu++K'`

Not included in the post is the following Shue program (`p`):

```
print("Hello Shue")
(=p
?=(
K="
++=e
ooo=o
'=)

```

Note that there is a trailing space after the `o`

The first line is the program `h`. Next are a series of replacement rules. Let's see how they work.

With the input `(rint?KH++lloooShu++K'` (`i`) we can get to `h` like so

```
(rint?KH++lloooShu++K'
(rint(KH++lloooShu++K' - ?=(
print(KH++lloooShu++K' - (=p
print("H++lloooShu++K' - K="
print("H++lloooShu++K) - '=)
print("H++lloooShu++") - K="
print("H++llo Shu++")  - ooo=o
print("Hello Shu++")   - ++=e
print("Hello Shue")    - ++=e

```

If your code `h` contains equals signs, backslashes or newlines, escape them with `\=`,`\\` and `\n` respectively in the Shue program `p` (but not in the input `i`). If your code contains nulls or non-unicode bytes, don't worry, Shue is byte-oriented.

# Answer
# Python 3, score 163+563=726, Safe

> In this cops-and-robbers challenge, your task is to write a program h that outputs "Hello Shue!". Next, you have to choose a string i and also write a Shue program p, so that p(i)=h. Your score is len(p)+len(i). Your answer will contain the language of h, i and your score (please write the score as len(p)+len(i)=score). Robbers will try to find p. Note that any working p, that is as long as your p or shorter means that your answer is defeated, even if it wasn't the solution you intended. The undefeated cop answer with the smallest score wins (per language).

Not that fun though

```
print("Hello Shue")
I=
n=
 =
t=
h=
i=
s=
c=
o=
-=
a=
d=
b=
e=
r=
l=
g=
,=
y=
u=
k=
w=
p=
m=
.=
N=
x=
v=
S=
(=
)=
\==
Y=
+=
f=
R=
'=
T=
=nt(

```

actually 140 bytes
> 2 votes

# Answer
# Vyxal, score 28+19=47

```
\a:ȯ≤∨I:C‹C\Hp5‛ SṀṅ

```

Try input online!
I don't know if it'll be an easy crack, or if I forgot something.
> 2 votes

---
Tags: cops-and-robbers, code-generation, hello-world
---


title: Play 1D minesweeper

text:
# Question
Title: Play 1D minesweeper
Your input is an array of integers in the range `[-1,4]`. An array element of `-1` means that there might be a bomb in that position. A non-negative element means that there is not a bomb in that position and also the numeric value tells how many bombs there are **within distance 2**.

For example, if we have the following array: `[1,2,-1,-1,4,-1,-1,-1,1]` it's possible to infer that every `-1` except the last one contains a bomb.

Your task is to take indicate which `-1` **for sure doesn't** contain a bomb by outputting it's index (0 or 1 based). There is always at least one guranteed bombfree square (and thus the input length is at least two). You can use another number instead of `-1` to represent an unknown square. If there are multiple possibilities output at least one of them. Shortest code wins.

To reiterate, you **have to be certain** that the index you output **cannot contain a mine**. If you were clearing mines IRL, you probably would also like to know that you won't accidentally step on one.

# Test cases

```
[-1,0] -> 0
[0,1,-1,-1] -> 2
[-1,-1,-1,0] -> 1 or 2
[1,-1,-1,-1,2] -> 1
[-1,2,-1,-1,4,-1,-1] -> 0
[-1,-1,3,-1,-1,2,2,-1] -> 3
[2,-1,-1,-1,2,-1,-1,-1,2] -> 3 or 5
[-1,-1,1,-1,-1,-1,-1,1,0] -> 6
[-1,-1,1,-1,-1,2,-1,-1,2,-1,-1,2,-1,1] -> 0 or 1

```

# Answer
# Charcoal, ~~55~~ ~~48~~ 47 bytes

```
≔⌕Ａθ±¹ηＦＥＸ²ＬηΦη﹪÷ιＸ²μ²Ｆ⬤θ∨‹κ⁰⁼κＬΦι›³↔⁻μλ≔⁻ηιηＩη

```

Try it online! Link is to verbose version of code. Outputs all possible bombfree positions. Explanation:

```
≔⌕Ａθ±¹η

```

Create a list of all the positions of `-1`s in the input.

```
ＦＥＸ²ＬηΦη﹪÷ιＸ²μ²

```

Create all possible mine layouts and loop over them.

```
Ｆ⬤θ∨‹κ⁰⁼κＬΦι›³↔⁻μλ

```

If for all non-negative values there are the correct number of mines within a distance of 2, then...

```
≔⁻ηιη

```

... remove the positions that might have a mine.

```
Ｉη

```

Output the positions that didn't have a mine.
> 6 votes

# Answer
# Wolfram Language (Mathematica), 102 bytes

```
Position[#+Total@Cases[{0,1}~Tuples~Tr[1^#],v_/;MatchQ[ListConvolve[{1,1,5,1,1},v,3,0],#/.-1->_]],-1]&

```

Try it online!

A port of my PARI/GP answer. 1-indexed.
> 2 votes

# Answer
# Pari/GP, 110 bytes

```
a->forvec(v=[[k=0,1]|i<-s=a],i=1;[t+1|t<-a,polcoef(Polrev(v)*Pol([1,1,5,1,1]),i++)!=t]||s+=v);[k|t<-s,t<0*k++]

```

Try it online!

1-indexed.

Ungolfed:

```
{ a ->                              /* Define a function with argument a: */
    s = a;                          /* Let s = a. */
    forvec(v = [[0, 1] | i <- a],   /* Let v loops over all binary vectors with length #a. */
        if(                         /* If */
            prod(i = 1, #a,         /* for all i in range 1..#a */
                a[i] == -1 ||       /* a[i] is -1 or */
                polcoef(            /* the coefficient of x^(i + 1) in */
                    Polrev(v)       /* the polynomial with coefficients v */
                    * Pol([1 ,1, 5, 1, 1]),     /* times (1 + x + 5*x^2 + x^3 + x^4) */
                    i + 1
                ) == a[i]           /* equals a[i] */
            ),
            s += v                  /* Then add v to s */
        )
    );
    [k | k <- [1..#a], s[k] == -1]  /* Find all k in range 1..#a such that s[k] is -1 */
}

```
> 2 votes

# Answer
# JavaScript (ES6), 127 bytes

The output is 0-indexed.

```
a=>a.findIndex((v,i)=>!~v&[...Array(1<<a.length)].every((_,k)=>a.some((v,j)=>~v*(g=x=>x+3?g(x-1)-(!~a[x+=j]&k>>x|x==i):v)(2))))

```

Try it online!

---

# JavaScript (ES6), 118 bytes

Slightly shorter but stack-overflows on the last test case.

```
a=>a.findIndex((v,i)=>!~v&(h=k=>k>>a.length||a.some((v,j)=>~v*(g=x=>x+3?g(x-1)-(!~a[x+=j]&k>>x|x==i):v)(2))&h(-~k))())

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 112 bytes

```
a=>eval("for(i=k=-1;j=4*--i;~a[k]|i>>k&!a.some(v=>((j&9)+(j/2&9))*9/8&7^v|(j/=2)&2&&~v)&&(i=2**a.length,k++))k")

```

Try it online!

```
// for each cell `k`
// for each possible mine placement `i`
// convert `i` to binary, the nth lsb  means nth cell is a mine
for(i=k=0;++i<2**a.length;)
  if(
    // Current cell is not unknown, or
    ~a[k]|
    // current mine placement have a mine on position `k`, and
    i>>k&
    // it is a valid mine placement
    !a.some(v=>
      // (mine count is incorrect or current is mine) and current is not -1
      ((j&9)+(j/2&9))*9/8&7^v|(j/=2)&2&&~v,j=i*4)
  // we try next `k`
  )i=0,k++;

```
> 1 votes

# Answer
# Python NumPy, 127 bytes

```
lambda L:where(L<-sum((T:=r_[:1<<(l:=len(L))]>>(a:=c_[:l])&1)*~any(((5//-~abs(a-a.T<<1)@T).T-L)*~L,1),1))[0]
from numpy import*
```

Attempt This Online!

### Old Python NumPy, 134 bytes (@alephalpha)

```
def f(L):t=len(L);T=c_[:1<<t]>>r_[:t]&1;return where(L<-sum(T[~any((T@triu(tril(L**0,2),-2)+4*T-L)*(L+1),1)],0))[0]
from numpy import*
```

Attempt This Online!

### Old Python NumPy, 141 bytes

```
def f(L):m=L<0;t=sum(m);T=c_[:1<<t]>>r_[:t]&1;v=any((T@triu(tril(L**0,2),-2)[m]-L)*~m,1);return where(m)[0][~any(T[~v],0)]
from numpy import*
```

Attempt This Online!

### Old Python NumPy, 149 bytes

```
def f(L):m=L<0;M=triu(tril(L**0),-2);t=sum(m);T=c_[:1<<t]>>r_[:t]&1;v=any((T@(M^M.T)[m]-L)*~m,1);return where(m)[0][~any(T[~v],0)]
from numpy import*
```

Attempt This Online!

Brute-force approach using matrix algebra. Takes a numpy array and returns the indices (0-based) of all safe squares.

Matrix `T` contains all patterns of bombs at -1 positions as columns. `triu(tril...` is essentially an adjacency matrix capturing the geometry of hint/bomb squares. By multiplying T with this matrix we get for each pattern in `T` the corresponding pattern of hints it would generate. A square is safe if each pattern of bombs where it is set creates a pattern of hints that is not the given one.
> 1 votes

# Answer
# 05AB1E, 38 bytes

```
®Qƶ0K<ÐUæʒXðrKǝ₂S.øü5ʒÅsd}εÅsy®¢Q}P}˜K

```

Outputs all possible results.

Inspired by *@Neil*'s Charcoal answer.

Try it online or verify all test cases or try it online with added debug-lines.

**Explanation:**

```
®Qƶ0K<        # Get a list of (0-based) indices of the -1s:
              # (05AB1E unfortunately lacks a builtin for this..)
®Q            #  Check for each value in the (implicit) input-list if its equal to -1
  ƶ           #  Multiply each (0 or 1) check by its 1-based index
   0K         #  Remove all 0s
     <        #  Decrease the 1-based indices to 0-based indices
Ð             # Triplicate this list of bomb-indices
 U            # Pop and store one of them in variable `X`
 æ            # Pop another one and get its powerset
  ʒ           # Filter this powerset by:
              #  (implicitly push the current powerset-list)
   X          #  Push list `X` with the bomb-indices
    ð         #  Push a space character
     r        #  Reverse so the stack-order goes to space, `X`, powerset-list
      K       #  Remove the values of the powerset-list from bomb-indices list `X`
       ǝ      #  Replace those bombs with spaces in the (implicit) input-list,
              #  to mark those bombs as duds
        ₂S.ø  #  Surround this list with leading/trailing [2,6]
              #  (any leading/trailing pair that isn't -1 would be fine here)
   ü5         #  Pop and push all overlapping quintuplets
     ʒ        #  Filter this list of quintuplets by, keeping those where:
      Ås      #   The middle item
        d     #   is a non-negative integer (so neither a -1 bomb nor " " dud)
     }ε       #  After the inner filter: map over the remaining quintuplets
       Ås     #   Check if the middle item
            Q #   is equal to
         y®¢  #   the amount of -1 bombs
      }P      #  After the map: check if all were truthy by taking the product
  }˜          # After the filter: flatten the list of powersets that were truthy
    K         # Remove those from the bomb-indices list we've triplicated at the start
              # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Python3, 580 bytes:

```
def r(d,p,v):
 d,c=eval(str(d)),[]
 for i in p:
  if 0<=i and i<len(d)and d[i]<0:d[i]=v;c+=[1]
 return c and[d]
def f(d,c=0):
 def g(d,c,o,u):
  if o==1:
   for i in r(d,[c-1],u)+r(d,[c+1],u):yield from f([*i],c+1)
   return
  for i in r(d,[c-2,c-1],u)+r(d,[c+1,c+2],u):yield from f([*i],c+1)
 if len(d)==c:yield d;return
 if d[c]in[2,1,0]:yield from g(d,c,d[c],[-2,-3][d[c]==0])
 else:yield from f(d,c+1)
def F(d):
 v={}
 for i in f(d):
  if -3 in i:return i.index(-3)
  for j,k in enumerate(i):
   if k==-2:v[j]=v.get(j,0)+1
 return min(v,key=lambda x:v[x])if v else d.index(-1)

```

Try it online!
> 0 votes

# Answer
# Python 3, ~~408~~404 bytes

```
e=enumerate
def v(m):
 for i,u in e(m):
  if u>-1 and m[max(0,i-2):i+3].count(-2)>u:return 0
 return 1
def p(m):
 for i,u in e(m):
  if u>0 and m[max(0,i-2):i+3].count(-2)<u:return 1
 return 0
def b(m):
 r=[]
 for i,u in e(m):
  if u==-1:t=m.copy();t[i]=-2;r+=b(t)if p(t)else[t]if v(t)else[]
 return r
def s(m):
 t=b(m)
 for i,u in e(m):
  if u==-1:
   n=1
   for u in t:
    if u[i]==-2:n=0
   if n:return i

```

Try it online!

Saved 4 bytes with suggestion from Neil
> 0 votes

---
Tags: code-golf, minesweeper
---


# Question
Title: Bentley's coding challenge: k most frequent words
This is perhaps one of the classical coding challenges that got some resonance in 1986, when columnist Jon Bentley asked Donald Knuth to write a program that would find k most frequent words in a file. Knuth implemented a fast solution using hash tries in an 8-pages-long program to illustrate his literate programming technique. Douglas McIlroy of Bell Labs criticized Knuth's solution as not even able to process a full text of the Bible, and replied with a one-liner, that is not as quick, but gets the job done:

```
tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q

```

In 1987, a follow up article was published with yet another solution, this time by a Princeton professor. But it also couldn't even return result for a single Bible!

## Problem description

Original problem description:

> Given a text file and an integer k, you are to print the k most common words in the file (and the number of their occurrences) in decreasing frequency.

Additional problem clarifications:

* Knuth defined a words as a string of Latin letters: `[A-Za-z]+`
* all other characters are ignored
* uppercase and lowercase letters are considered equivalent (`WoRd` == `word`)
* no limit on file size nor word length
* distances between consecutive words can be arbitrarily large
* fastest program is the one that uses least total CPU time (multithreading probably won't help)

## Sample test cases

**Test 1:** *Ulysses* by James Joyce concatenated 64 times (96 MB file).

* Download *Ulysses* from Project Gutenberg: `wget http://www.gutenberg.org/files/4300/4300-0.txt`
* Concatenate it 64 times: `for i in {1..64}; do cat 4300-0.txt >> ulysses64; done`
* Most frequent word is “the” with 968832 appearances.

**Test 2:** Specially generated random text `giganovel` (around 1 GB).

* Python 3 generator script here.
* The text contains 148391 distinct words appearing similarly to natural languages.
* Most frequent words: “e” (11309 appearances) and “ihit” (11290 appearances).

**Generality test:** arbitrarily large words with arbitrarily large gaps.

## Reference implementations

After looking into Rosetta Code for this problem and realizing that many implementations are incredibly slow (slower than the shell script!), I tested a few good implementations here. Below is the performance for `ulysses64` together with time complexity:

```
                                     ulysses64      Time complexity
C++ (prefix trie + heap)             4.145          O((N + k) log k)
Python (Counter)                     10.547         O(N + k log Q)
GNU awk + sort                       20.606         O(N + Q log Q)
McIlroy (tr + sort + uniq)           43.554         O(N log N)

```

Can you beat that?

## Testing

Performance will be evaluated using 2017 13" MacBook Pro with the standard Unix `time` command ("user" time). If possible, please, use modern compilers (e.g., use the latest Haskell version, not the legacy one).

## Rankings so far

Timings, including the reference programs:

```
                                              k=10                  k=100K
                                     ulysses64      giganovel      giganovel
Rust (trie-32) by Tethys Svensson    0.524          3.576          3.593
Rust (trie-32) by test9753           0.622          4.139          4.157
C++ (trie-32) by ShreevatsaR         0.671          4.227          4.276
C (trie + bins) by Moogie            0.704          9.568          9.459
C (trie + list) by Moogie            0.767          6.051          82.306
C++ (hash trie) by ShreevatsaR       0.788          5.283          5.390
C (trie + sorted list) by Moogie     0.804          7.076          x
Rust (trie) by Anders Kaseorg        0.842          6.932          7.503
J by miles                           1.273          22.365         22.637
mawk-2 + sort                        2.763          28.488         29.329
OCaml by test9753                    3.615          47.432         262.714
C# (trie) by recursive               3.722          25.378         24.771
C++ (trie + heap)                    4.145          42.631         72.138
APL (Dyalog Unicode) by Adám         7.680          x              x
Scala (mutable.Map) by lprakashv     9.269          56.019         54.946
Python (dict) by movatica            9.387          99.118         100.859
Python (Counter)                     10.547         102.822        103.930
Ruby (tally) by daniero              15.139         171.095        171.551
gawk + sort                          20.529         213.366        222.782
McIlroy (tr + sort + uniq)           43.554         715.602        750.420

```

Cumulative ranking\* (%, best possible score – 300):

```
#     Program                           Score  Generality
 1  Rust (trie-32) by Tethys Svensson     300     Yes
 2  Rust (trie-32) by test9753            350     Yes
 3  C++ (trie-32) by ShreevatsaR          365     Yes
 4  C++ (hash trie) by ShreevatsaR        448      x
 5  Rust (trie) by Anders Kaseorg         563     Yes
 6  C (trie + bins) by Moogie             665      x
 7  J by miles                           1498     Yes
 8  C# (trie) by recursive               2109      x
 9  mawk-2 + sort                        2140     Yes
10  C (trie + list) by Moogie            2606      x
11  C++ (trie + heap)                    3991      x
12  Scala (mutable.Map) by lprakashv     4865     Yes
13  Python (dict) by movatica            7370     Yes
14  Python (Counter)                     7781     Yes
15  OCaml by test9753                    9328     Yes
16  Ruby (tally) by daniero             12448     Yes
17  gawk + sort                         16085     Yes
18  McIlroy (tr + sort + uniq)          49209     Yes

```

\*Sum of time performance relative to the best programs in each of the three tests.

Best program so far: **here**

# Answer
## \[Rust\] Optimized version of test9753's code

I changed a few details (e.g. pre-processing the data and splitting up the parent links from child links) while also making the code a bit more idiomatic.

On my machine this runs the giganovel about 20% faster.

```
use std::env;
use std::io::{Error, ErrorKind};

type Pointer = i32;
type Count = i32;
type Char = u8;

#[derive(Copy, Clone)]
struct Node {
    link: Pointer,
    count: Count,
}

fn word_for(parents: &[Pointer], mut p: Pointer) -> String {
    let mut drow = Vec::with_capacity(25); // sane max length
    while p != -1 {
        let c = p % 26;
        p = parents[(p / 26) as usize];
        drow.push(b'a' + (c as Char));
    }
    drow.reverse();
    String::from_utf8(drow).unwrap()
}

fn create_child(
    parents: &mut Vec<Pointer>,
    children: &mut Vec<Node>,
    p: Pointer,
    c: Char,
) -> Pointer {
    let h = children.len();
    children[p as usize].link = h as Pointer;
    children.resize(children.len() + 26, Node { link: -1, count: 0 });
    parents.push(p);
    (h as u32 + c as u32) as Pointer
}

fn find_child(
    parents: &mut Vec<Pointer>,
    children: &mut Vec<Node>,
    p: Pointer,
    c: Char,
) -> Pointer {
    let elem = children[p as usize];
    if elem.link == -1 {
        create_child(parents, children, p, c)
    } else {
        (elem.link as u32 + c as u32) as Pointer
    }
}

fn error(msg: &str) -> Error {
    Error::new(ErrorKind::Other, msg)
}

fn main() -> std::io::Result<()> {
    let args = env::args().collect::<Vec<String>>();
    if args.len() != 3 {
        return Err(error(&format!(
            "Usage: {} file-path limit-num",
            env::args().next().unwrap()
        )));
    }
    let mut data: Vec<u8> = std::fs::read(&args[1])?;
    for d in &mut data {
        *d = (*d | 32) - b'a';
    }

    let mut children: Vec<Node> = Vec::with_capacity(data.len() / 600);
    let mut parents: Vec<Pointer> = Vec::with_capacity(data.len() / 600 / 26);
    parents.push(-1);
    for _ in 0..26 {
        children.push(Node { link: -1, count: 0 });
    }

    let mut data = data.iter();

    while let Some(&c) = data.next() {
        if c < 26 {
            let mut p = c as Pointer;

            while let Some(&c) = data.next() {
                if c < 26 {
                    p = find_child(&mut parents, &mut children, p, c);
                } else {
                    break;
                }
            }
            children[p as usize].count += 1;
        }
    }

    let mut counts_words: Vec<(i32, String)> = Vec::new();
    for (i, e) in children.iter().enumerate() {
        if e.count != 0 {
            counts_words.push((-e.count, word_for(&parents, i as Pointer)));
        }
    }

    counts_words.sort();

    let limit = args[2]
        .parse()
        .map_err(|_| error("ARGV[2] must be in range: [1, usize_max]"))?;

    for (count, word) in counts_words.iter().take(limit) {
        println!("{word} {count}", word = word, count = -count);
    }

    Ok(())
}

```
> 9 votes

# Answer
# C++ (a la Knuth)

I was curious how Knuth's program would fare, so I translated his (originally Pascal) program into C++.

Even though Knuth's primary goal was not speed but to illustrate his WEB system of literate programming, the program is surprisingly competitive, and leads to a faster solution than any of the answers here so far. Here's my translation of his program (the corresponding "section" numbers of the WEB program are mentioned in comments like "`{§24}`"):

```
#include <iostream>
#include <cassert>

// Adjust these parameters based on input size.
const int TRIE_SIZE = 800 * 1000; // Size of the hash table used for the trie.
const int ALPHA = 494441;  // An integer that's approximately (0.61803 * TRIE_SIZE), and relatively prime to T = TRIE_SIZE - 52.
const int kTolerance = TRIE_SIZE / 100;  // How many places to try, to find a new place for a "family" (=bunch of children).

typedef int32_t Pointer;  // [0..TRIE_SIZE), an index into the array of Nodes
typedef int8_t Char;  // We only care about 1..26 (plus two values), but there's no "int5_t".
typedef int32_t Count;  // The number of times a word has been encountered.
// These are 4 separate arrays in Knuth's implementation.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Pointer sibling;  // Previous sibling, cyclically. (From smallest child to header, and header to largest child.)
  Count count;  // The number of times this word has been encountered.
  Char ch;  // EMPTY, or 1..26, or HEADER. (For nodes with ch=EMPTY, the link/sibling/count fields mean nothing.)
} node[TRIE_SIZE + 1];
// Special values for `ch`: EMPTY (free, can insert child there) and HEADER (start of family).
const Char EMPTY = 0, HEADER = 27;

const Pointer T = TRIE_SIZE - 52;
Pointer x;  // The `n`th time we need a node, we'll start trying at x_n = (alpha * n) mod T. This holds current `x_n`.
// A header can only be in T (=TRIE_SIZE-52) positions namely [27..TRIE_SIZE-26].
// This transforms a "h" from range [0..T) to the above range namely [27..T+27).
Pointer rerange(Pointer n) {
  n = (n % T) + 27;
  // assert(27 <= n && n <= TRIE_SIZE - 26);
  return n;
}

// Convert trie node to string, by walking up the trie.
std::string word_for(Pointer p) {
  std::string word;
  while (p != 0) {
    Char c = node[p].ch;  // assert(1 <= c && c <= 26);
    word = static_cast<char>('a' - 1 + c) + word;
    // assert(node[p - c].ch == HEADER);
    p = (p - c) ? node[p - c].link : 0;
  }
  return word;
}

// Increment `x`, and declare `h` (the first position to try) and `last_h` (the last position to try). {§24}
#define PREPARE_X_H_LAST_H x = (x + ALPHA) % T; Pointer h = rerange(x); Pointer last_h = rerange(x + kTolerance);
// Increment `h`, being careful to account for `last_h` and wraparound. {§25}
#define INCR_H { if (h == last_h) { std::cerr << "Hit tolerance limit unfortunately" << std::endl; exit(1); } h = (h == TRIE_SIZE - 26) ? 27 : h + 1; }

// `p` has no children. Create `p`s family of children, with only child `c`. {§27}
Pointer create_child(Pointer p, int8_t c) {
  // Find `h` such that there's room for both header and child c.
  PREPARE_X_H_LAST_H;
  while (!(node[h].ch == EMPTY and node[h + c].ch == EMPTY)) INCR_H;
  // Now create the family, with header at h and child at h + c.
  node[h]     = {.link = p, .sibling = h + c, .count = 0, .ch = HEADER};
  node[h + c] = {.link = 0, .sibling = h,     .count = 0, .ch = c};
  node[p].link = h;
  return h + c;
}

// Move `p`'s family of children to a place where child `c` will also fit. {§29}
void move_family_for(const Pointer p, Char c) {
  // Part 1: Find such a place: need room for `c` and also all existing children. {§31}
  PREPARE_X_H_LAST_H;
  while (true) {
    INCR_H;
    if (node[h + c].ch != EMPTY) continue;
    Pointer r = node[p].link;
    int delta = h - r;  // We'd like to move each child by `delta`
    while (node[r + delta].ch == EMPTY and node[r].sibling != node[p].link) {
      r = node[r].sibling;
    }
    if (node[r + delta].ch == EMPTY) break;  // There's now space for everyone.
  }

  // Part 2: Now actually move the whole family to start at the new `h`.
  Pointer r = node[p].link;
  int delta = h - r;
  do {
    Pointer sibling = node[r].sibling;
    // Move node from current position (r) to new position (r + delta), and free up old position (r).
    node[r + delta] = {.ch = node[r].ch, .count = node[r].count, .link = node[r].link, .sibling = node[r].sibling + delta};
    if (node[r].link != 0) node[node[r].link].link = r + delta;
    node[r].ch = EMPTY;
    r = sibling;
  } while (node[r].ch != EMPTY);
}

// Advance `p` to its `c`th child. If necessary, add the child, or even move `p`'s family. {§21}
Pointer find_child(Pointer p, Char c) {
  // assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // If `p` currently has *no* children.
  Pointer q = node[p].link + c;
  if (node[q].ch == c) return q;  // Easiest case: `p` already has a `c`th child.
  // Make sure we have room to insert a `c`th child for `p`, by moving its family if necessary.
  if (node[q].ch != EMPTY) {
    move_family_for(p, c);
    q = node[p].link + c;
  }
  // Insert child `c` into `p`'s family of children (at `q`), with correct siblings. {§28}
  Pointer h = node[p].link;
  while (node[h].sibling > q) h = node[h].sibling;
  node[q] = {.ch = c, .count = 0, .link = 0, .sibling = node[h].sibling};
  node[h].sibling = q;
  return q;
}

// Largest descendant. {§18}
Pointer last_suffix(Pointer p) {
  while (node[p].link != 0) p = node[node[p].link].sibling;
  return p;
}

// The largest count beyond which we'll put all words in the same (last) bucket.
// We do an insertion sort (potentially slow) in last bucket, so increase this if the program takes a long time to walk trie.
const int MAX_BUCKET = 10000;
Pointer sorted[MAX_BUCKET + 1];  // The head of each list.

// Records the count `n` of `p`, by inserting `p` in the list that starts at `sorted[n]`.
// Overwrites the value of node[p].sibling (uses the field to mean its successor in the `sorted` list).
void record_count(Pointer p) {
  // assert(node[p].ch != HEADER);
  // assert(node[p].ch != EMPTY);
  Count f = node[p].count;
  if (f == 0) return;
  if (f < MAX_BUCKET) {
    // Insert at head of list.
    node[p].sibling = sorted[f];
    sorted[f] = p;
  } else {
    Pointer r = sorted[MAX_BUCKET];
    if (node[p].count >= node[r].count) {
      // Insert at head of list
      node[p].sibling = r;
      sorted[MAX_BUCKET] = p;
    } else {
      // Find right place by count. This step can be SLOW if there are too many words with count >= MAX_BUCKET
      while (node[p].count < node[node[r].sibling].count) r = node[r].sibling;
      node[p].sibling = node[r].sibling;
      node[r].sibling = p;
    }
  }
}

// Walk the trie, going over all words in reverse-alphabetical order. {§37}
// Calls "record_count" for each word found.
void walk_trie() {
  // assert(node[0].ch == HEADER);
  Pointer p = node[0].sibling;
  while (p != 0) {
    Pointer q = node[p].sibling;  // Saving this, as `record_count(p)` will overwrite it.
    record_count(p);
    // Move down to last descendant of `q` if any, else up to parent of `q`.
    p = (node[q].ch == HEADER) ? node[q].link : last_suffix(q);
  }
}

int main(int, char** argv) {
  // Program startup
  std::ios::sync_with_stdio(false);

  // Set initial values {§19}
  for (Char i = 1; i <= 26; ++i) node[i] = {.ch = i, .count = 0, .link = 0, .sibling = i - 1};
  node[0] = {.ch = HEADER, .count = 0, .link = 0, .sibling = 26};

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0L, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  if (fptr) fclose(fptr);

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (int i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  node[0].count = 0;

  walk_trie();

  const int max_words_to_print = atoi(argv[2]);
  int num_printed = 0;
  for (Count f = MAX_BUCKET; f >= 0 && num_printed <= max_words_to_print; --f) {
    for (Pointer p = sorted[f]; p != 0 && num_printed < max_words_to_print; p = node[p].sibling) {
      std::cout << word_for(p) << " " << node[p].count << std::endl;
      ++num_printed;
    }
  }

  return 0;
}

```

Differences from Knuth's program:

* I combined Knuth's 4 arrays `link`, `sibling`, `count` and `ch` into an array of a `struct Node` (find it easier to understand this way).
* I changed the literate-programming (WEB-style) textual transclusion of sections into more conventional function calls (and a couple of macros).
* We don't need to use standard Pascal's weird I/O conventions/restrictions, so using `fread` and `data[i] | 32 - 'a'` as in the other answers here, instead of the Pascal workaround.
* In case we exceed limits (run out of space) while the program is running, Knuth's original program deals with it gracefully by dropping later words, and printing a message at the end. (It's not quite right to say that McIlroy "criticized Knuth's solution as not even able to process a full text of the Bible"; he was only pointing out that sometimes frequent words may occur very late in a text, such as the word "Jesus" in the Bible, so the error condition is not innocuous.) I've taken the noisier (and anyway easier) approach of simply terminating the program.
* The program declares a constant TRIE\_SIZE to control the memory usage, which I bumped up. (The constant of 32767 had been chosen for the original requirements -- "a user should be able to find the 100 most frequent words in a twenty-page technical paper (roughly a 50K byte file)" and because Pascal deals well with ranged integer types and packs them optimally. We had to increase it 25x to 800,000 as test input is now 20 million times larger.)
* For the final printing of strings, we can just walk the trie and do a dumb (possibly even quadratic) string append.

Apart from that, this is pretty much exactly Knuth's program (using his hash trie / packed trie data structure and bucket sort), and does pretty much the same operations (as Knuth's Pascal program would) while looping through all characters in the input; note that it uses no external algorithm or data structure libraries, and also that words of equal frequency will be printed in alphabetical order.

## Timing

Compiled with

```
clang++ -std=c++17 -O2 ptrie-walktrie.cc

```

When run on the largest testcase here (`giganovel` with 100,000 words requested), and compared against the fastest program posted here so far, I find it slightly but consistently faster:

```
target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]

```

(The top line is Anders Kaseorg's Rust solution; the bottom is the above program. These are timings from 100 runs, with mean, min, max, median, and quartiles.)

## Analysis

Why is this faster? It is not that C++ is faster than Rust, or that Knuth's program is the fastest possible -- in fact, Knuth's program is slower on insertions (as he mentions) because of the trie-packing (to conserve memory). The reason, I suspect, is related to something that Knuth complained about in 2008:

> A Flame About 64-bit Pointers
>
> It is absolutely idiotic to have 64-bit pointers when I compile a program that uses less than 4 gigabytes of RAM. When such pointer values appear inside a struct, they not only waste half the memory, they effectively throw away half of the cache.

The program above uses 32-bit array indices (not 64-bit pointers), so the "Node" struct occupies less memory, so there are more Nodes on the stack and fewer cache misses. (In fact, there was some work on this as the x32 ABI, but it seems to be not in a good state even though the idea is obviously useful, e.g. see the recent announcement of pointer compression in V8. Oh well.) So on `giganovel`, this program uses 12.8 MB for the (packed) trie, versus the Rust program's 32.18MB for its trie (on `giganovel`). We could scale up 1000x (from "giganovel" to "teranovel" say) and still not exceed 32-bit indices, so this seems a reasonable choice.

# Faster variant

We can optimize for speed and forego the packing, so we can actually use the (non-packed) trie as in the Rust solution, with indices instead of pointers. This gives something that's faster *and* has no pre-fixed limits on number of distinct words, characters etc:

```
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

typedef int32_t Pointer;  // [0..node.size()), an index into the array of Nodes
typedef int32_t Count;
typedef int8_t Char;  // We'll usually just have 1 to 26.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Count count;  // The number of times this word has been encountered. Undefined for header nodes.
};
std::vector<Node> node; // Our "arena" for Node allocation.

std::string word_for(Pointer p) {
  std::vector<char> drow;  // The word backwards
  while (p != 0) {
    Char c = p % 27;
    drow.push_back('a' - 1 + c);
    p = (p - c) ? node[p - c].link : 0;
  }
  return std::string(drow.rbegin(), drow.rend());
}

// `p` has no children. Create `p`s family of children, with only child `c`.
Pointer create_child(Pointer p, Char c) {
  Pointer h = node.size();
  node.resize(node.size() + 27);
  node[h] = {.link = p, .count = -1};
  node[p].link = h;
  return h + c;
}

// Advance `p` to its `c`th child. If necessary, add the child.
Pointer find_child(Pointer p, Char c) {
  assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // Case 1: `p` currently has *no* children.
  return node[p].link + c;  // Case 2 (easiest case): Already have the child c.
}

int main(int, char** argv) {
  auto start_c = std::clock();

  // Program startup
  std::ios::sync_with_stdio(false);

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  fclose(fptr);

  node.reserve(dataLength / 600);  // Heuristic based on test data. OK to be wrong.
  node.push_back({0, 0});
  for (Char i = 1; i <= 26; ++i) node.push_back({0, 0});

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (long i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  ++node[p].count;
  node[0].count = 0;

  // Brute-force: Accumulate all words and their counts, then sort by frequency and print.
  std::vector<std::pair<int, std::string>> counts_words;
  for (Pointer i = 1; i < static_cast<Pointer>(node.size()); ++i) {
    int count = node[i].count;
    if (count == 0 || i % 27 == 0) continue;
    counts_words.push_back({count, word_for(i)});
  }
  auto cmp = [](auto x, auto y) {
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
  };
  std::sort(counts_words.begin(), counts_words.end(), cmp);
  const int max_words_to_print = std::min<int>(counts_words.size(), atoi(argv[2]));
  for (int i = 0; i < max_words_to_print; ++i) {
    auto [count, word] = counts_words[i];
    std::cout << word << " " << count << std::endl;
  }

  return 0;
}

```

This program, despite doing something a lot dumber for sorting than the solutions here, uses (for `giganovel`) only 12.2MB for its trie, and manages to be faster. Timings of this program (last line), compared with the earlier timings mentioned:

```
target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]
itrie-nolimit:             3.907 ±   0.127 [ 3.69.. 4.23]        [... 3.81 ...   3.9 ...   4.0...]

```

I'd be eager to see what this (or the hash-trie program) would like if translated into Rust. :-)

## Further details

1. About the data structure used here: an explanation of "packing" tries is given tersely in Exercise 4 of Section 6.3 (Digital Searching, i.e. tries) in Volume 3 of TAOCP, and also in the thesis of Knuth's student Frank Liang about hyphenation in TeX: Word Hy-phen-a-tion by Com-put-er.
2. The context of Bentley's columns, Knuth's program, and McIlroy's review (only a small part of which was about the Unix philosophy) is clearer in light of previous and later columns, and Knuth's previous experience including compilers, TAOCP, and TeX.
3. There's an entire book *Exercises in Programming Style*, showing different approaches to this particular program, etc.

I have an unfinished blog post elaborating on the points above; might edit this answer when it's done. Meanwhile, posting this answer here anyway, on the occasion (Jan 10) of Knuth's birthday. :-)
> 15 votes

# Answer
# Rust

On my computer, this runs giganovel 100000 about 42% faster (10.64 s vs. 18.24 s) than Moogie’s C “prefix tree + bins” C solution. Also it has no predefined limits (unlike the C solution which predefines limits on word length, unique words, repeated words, etc.).

### `src/main.rs`

```
use memmap::MmapOptions;
use pdqselect::select_by_key;
use std::cmp::Reverse;
use std::default::Default;
use std::env::args;
use std::fs::File;
use std::io::{self, Write};
use typed_arena::Arena;

#[derive(Default)]
struct Trie<'a> {
    nodes: [Option<&'a mut Trie<'a>>; 26],
    count: u64,
}

fn main() -> io::Result<()> {
    // Parse arguments
    let mut args = args();
    args.next().unwrap();
    let filename = args.next().unwrap();
    let size = args.next().unwrap().parse().unwrap();

    // Open input
    let file = File::open(filename)?;
    let mmap = unsafe { MmapOptions::new().map(&file)? };

    // Build trie
    let arena = Arena::new();
    let mut num_words = 0;
    let mut root = Trie::default();
    {
        let mut node = &mut root;
        for byte in &mmap[..] {
            let letter = (byte | 32).wrapping_sub(b'a');
            if let Some(child) = node.nodes.get_mut(letter as usize) {
                node = child.get_or_insert_with(|| {
                    num_words += 1;
                    arena.alloc(Default::default())
                });
            } else {
                node.count += 1;
                node = &mut root;
            }
        }
        node.count += 1;
    }

    // Extract all counts
    let mut index = 0;
    let mut counts = Vec::with_capacity(num_words);
    let mut stack = vec![root.nodes.iter()];
    'a: while let Some(frame) = stack.last_mut() {
        while let Some(child) = frame.next() {
            if let Some(child) = child {
                if child.count != 0 {
                    counts.push((child.count, index));
                    index += 1;
                }
                stack.push(child.nodes.iter());
                continue 'a;
            }
        }
        stack.pop();
    }

    // Find frequent counts
    select_by_key(&mut counts, size, |&(count, _)| Reverse(count));
    // Or, in nightly Rust:
    //counts.partition_at_index_by_key(size, |&(count, _)| Reverse(count));

    // Extract frequent words
    let size = size.min(counts.len());
    counts[0..size].sort_by_key(|&(_, index)| index);
    let mut out = Vec::with_capacity(size);
    let mut it = counts[0..size].iter();
    if let Some(mut next) = it.next() {
        index = 0;
        stack.push(root.nodes.iter());
        let mut word = vec![b'a' - 1];
        'b: while let Some(frame) = stack.last_mut() {
            while let Some(child) = frame.next() {
                *word.last_mut().unwrap() += 1;
                if let Some(child) = child {
                    if child.count != 0 {
                        if index == next.1 {
                            out.push((word.to_vec(), next.0));
                            if let Some(next1) = it.next() {
                                next = next1;
                            } else {
                                break 'b;
                            }
                        }
                        index += 1;
                    }
                    stack.push(child.nodes.iter());
                    word.push(b'a' - 1);
                    continue 'b;
                }
            }
            stack.pop();
            word.pop();
        }
    }
    out.sort_by_key(|&(_, count)| Reverse(count));

    // Print results
    let stdout = io::stdout();
    let mut stdout = io::BufWriter::new(stdout.lock());
    for (word, count) in out {
        stdout.write_all(&word)?;
        writeln!(stdout, " {}", count)?;
    }

    Ok(())
}

```

### `Cargo.toml`

```
[package]
name = "frequent"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
memmap = "0.7.0"
typed-arena = "1.4.1"
pdqselect = "0.1.0"

[profile.release]
lto = true
opt-level = 3

```

### Usage

```
cargo build --release
time target/release/frequent ulysses64 10

```
> 8 votes

# Answer
**Rust translation of ShreevatsaR's "Faster variant"**

**Uses:**

```
$ cargo --version
cargo 1.41.0 (626f0f40e 2019-12-03)

$ rustc --version
rustc 1.41.0 (5e1a79984 2020-01-27)

```

**src/main.rs:**

```
use std::env;
use std::fs::File;
use std::io::{Error, ErrorKind, Read};
use std::string::String;
use std::vec::Vec;

type Pointer = u32;
type Count = i32;
type Char = u8;

#[repr(packed(8))]
#[derive(Copy, Clone)]
struct Node {
    link: Pointer,
    count: Count,
}

const MAX_STRING_LEN: usize = 25;
const ORD_A: Char = 97; // 'a'

fn word_for(nodes: &[Node], p: Pointer) -> String {
    let mut p = p;
    let mut drow = String::with_capacity(MAX_STRING_LEN);
    while p != 0 {
        let c = p % 27;
        drow.push(char::from(ORD_A - 1 + (c as Char)));
        let index = (p - c) as usize;
        if index != 0 {
            if let Some(elem) = nodes.get(index) {
                p = elem.link;
            } else {
                unreachable!();
            }
        } else {
            p = 0;
        }
    }
    drow.chars().rev().collect()
}

fn create_child(nodes: &mut Vec<Node>, p: Pointer, c: Char) -> Pointer {
    let h = nodes.len();
    nodes.resize(nodes.len() + 27, Node { link: 0, count: 0 });
    if let Some(elem) = nodes.get_mut(h) {
        *elem = Node { link: p, count: -1 };
    } else {
        unreachable!();
    }
    if let Some(el) = nodes.get_mut(p as usize) {
        el.link = h as Pointer;
    }
    (h as u32 + c as u32) as Pointer
}

fn find_child(nodes: &mut Vec<Node>, p: Pointer, c: Char) -> Pointer {
    assert!(1 <= c && c <= 26);
    if p == 0 {
        return c as Pointer;
    }
    if let Some(elem) = nodes.get(p as usize) {
        if elem.link == 0 {
            create_child(nodes, p, c)
        } else {
            (elem.link as u32 + c as u32) as Pointer
        }
    } else {
        unreachable!();
    }
}

fn error(msg: &str) -> Error {
    Error::new(ErrorKind::Other, msg)
}

fn main() -> std::io::Result<()> {
    if env::args().count() != 3 {
      return Err(error(&format!("Usage: {} file-path limit-num",
                     env::args().next().unwrap())));
    }
    let fname = env::args().nth(1).ok_or_else(|| error("Invalid ARGV[1]"))?;
    let mut file = File::open(fname)?;
    let file_size = file.metadata()?.len() as usize;
    let mut data: Vec<u8> = Vec::with_capacity(file_size);
    file.read_to_end(&mut data)?;

    let mut nodes: Vec<Node> = Vec::with_capacity(file_size / 600);
    for _ in 1..=27 {
        nodes.push(Node { link: 0, count: 0 });
    }

    {
        let mut p: Pointer = 0;
        for i in 0..file_size {
            if let Some(elem) = data.get(i) {
                let c: Char = (*elem | 32) - ORD_A + 1;
                if 1 <= c && c <= 26 {
                    p = find_child(&mut nodes, p, c);
                } else if let Some(el) = nodes.get_mut(p as usize) {
                    el.count += 1;
                    p = 0;
                } else {
                    unreachable!();
                }
            } else {
                unreachable!();
            }
        }

        if let Some(e) = nodes.get_mut(p as usize) {
            e.count += 1;
        } else {
            unreachable!();
        }

        if let Some(e) = nodes.get_mut(0) {
            e.count = 0;
        } else {
            unreachable!();
        }
    }

    struct Pair {
        count: i32,
        word: String,
    }

    let mut counts_words: Vec<Pair> = Vec::new();
    for i in 1..nodes.len() {
        if let Some(e) = nodes.get(i) {
            let count = e.count;
            if !((count == 0) || (i % 27 == 0)) {
                counts_words.push(Pair {
                    count,
                    word: word_for(&nodes, i as Pointer),
                });
            }
        } else {
            unreachable!();
        }
    }

    let cmp = |x: &Pair, y: &Pair| -> std::cmp::Ordering {
        if x.count != y.count {
            return y.count.cmp(&x.count);
        }
        x.word.cmp(&y.word)
    };

    counts_words.sort_by(cmp);

    let argv_2 = env::args().nth(2).ok_or_else(|| error("Invalid ARGV[2]"))?;
    let limit = usize::from_str_radix(&argv_2, 10)
        .map_err(|_| error("ARGV[2] must be in range: [1, usize_max]"))?;
    let max_words_to_print = std::cmp::min(counts_words.len(), limit);

    for cw in counts_words.iter().take(max_words_to_print) {
        println!("{word} {count}", word = cw.word, count = cw.count);
    }

    Ok(())
}

```

**Building:**

```
$ cargo build --release

```

**Testing:**

```
$ time ./target/release/bentley golf/ulysses64 10
the 968832
of 528960
and 466432
a 421184
to 322624
in 320512
he 270528
his 213120
i 191808
s 182144

real    0m1.408s
user    0m1.240s
sys     0m0.157s

```

**C++ "Faster variant" testing**

```
$ time golf/faster-variant golf/ulysses64 10
the 968832
of 528960
and 466432
a 421184
to 322624
in 320512
he 270528
his 213120
i 191808
s 182144

real    0m1.533s
user    0m1.411s
sys     0m0.109s

```
> 7 votes

# Answer
# \[C\]

The following runs in under 1.6 seconds for **Test 1** on my 2.8 Ghz Xeon W3530. Built using MinGW.org GCC-6.3.0-1 on Windows 7:

It takes two arguments as input (path to text file and for k number of most frequent words to list)

It simply creates a tree branching on letters of words, then at the leaf letters it increments a counter. Then checks to see if the current leaf counter is greater than the smallest most frequent word in the list of most frequent words. (list size is the number determined via the command line argument) If so then promote the word represented by the leaf letter to be one of the most frequent. This all repeats until no more letters are read in. After which the list of most frequent words are output via an inefficent iterative search for the most frequent word from the list of most frequent words.

It currently defaults to output the processing time, but for purposes of conistency with other submissions, disable the TIMING definition in the source code.

Also, I have submitted this from a work computer and have not been able to download Test 2 text. It should work with this Test 2 without modification, however the MAX\_LETTER\_INSTANCES value may need to be increased.

```
// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

// increase this if needing to output more top frequent words
#define MAX_TOP_FREQUENT_WORDS 1000

#define false 0
#define true 1
#define null 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    char mostFrequentWord;
    struct Letter* parent;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

int main(int argc, char *argv[])
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0 || k> MAX_TOP_FREQUENT_WORDS)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n");
        printf("NOTE: upto %d most frequent words can be requested\n\n",MAX_TOP_FREQUENT_WORDS);
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], 0, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;
    root->mostFrequentWord = false;
    root->count = 0;

    // the next letter to be processed
    Letter* nextLetter = null;

    // store of the top most frequent words
    Letter* topWords[MAX_TOP_FREQUENT_WORDS];

    // initialise the top most frequent words
    for (i = 0; i<k; i++)
    {
        topWords[i]=root;
    }

    unsigned int lowestWordCount = 0;
    unsigned int lowestWordIndex = 0;
    unsigned int highestWordCount = 0;
    unsigned int highestWordIndex = 0;

    // main loop
    for (int j=0;j<dataLength;j++)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                nextLetter = &letters[letterMasterIndex++];
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        // not a letter so this means the current letter is the last letter of a word (if any letters)
        else if (currentLetter!=root)
        {

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // ignore this word if already identified as a most frequent word
            if (!currentLetter->mostFrequentWord)
            {
                // update the list of most frequent words
                // by replacing the most infrequent top word if this word is more frequent
                if (currentLetter->count> lowestWordCount)
                {
                    currentLetter->mostFrequentWord = true;
                    topWords[lowestWordIndex]->mostFrequentWord = false;
                    topWords[lowestWordIndex] = currentLetter;
                    lowestWordCount = currentLetter->count;

                    // update the index and count of the next most infrequent top word
                    for (i=0;i<k; i++)
                    {
                        // if the topword  is root then it can immediately be replaced by this current word, otherwise test
                        // whether the top word is less than the lowest word count
                        if (topWords[i]==root || topWords[i]->count<lowestWordCount)
                        {
                            lowestWordCount = topWords[i]->count;
                            lowestWordIndex = i;
                        }
                    }
                }
            }

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

    // print out the top frequent words and counts
    char string[256];
    char tmp[256];

    while (k > 0 )
    {
        highestWordCount = 0;
        string[0]=0;
        tmp[0]=0;

        // find next most frequent word
        for (i=0;i<k; i++)
        {
            if (topWords[i]->count>highestWordCount)
            {
                highestWordCount = topWords[i]->count;
                highestWordIndex = i;
            }
        }

        Letter* letter = topWords[highestWordIndex];

        // swap the end top word with the found word and decrement the number of top words
        topWords[highestWordIndex] = topWords[--k];

        if (highestWordCount > 0)
        {
            // construct string of letters to form the word
            while (letter != root)
            {
                memmove(&tmp[1],&string[0],255);
                tmp[0]=letter->asciiCode+97;
                memmove(&string[0],&tmp[0],255);
                letter=letter->parent;
            }

            printf("%u %s\n",highestWordCount,string);
        }
    }

    free( data );
    free( letters );

#ifdef TIMING
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

```

For Test 1, and for the top 10 frequent words and with timing enabled it should print:

```
 968832 the
 528960 of
 466432 and
 421184 a
 322624 to
 320512 in
 270528 he
 213120 his
 191808 i
 182144 s

 Time Taken: 1.549155 seconds

```
> 5 votes

# Answer
# APL (Dyalog Unicode)

The following runs in under 8 seconds on my 2.6 Ghz i7-4720HQ using 64-bit Dyalog APL 17.0 on Windows 10:

```
⎕{m[⍺↑⍒⊢/m←{(⊂⎕UCS⊃⍺),≢⍵}⌸(⊢⊆⍨96∘<∧<∘123)83⎕DR 819⌶80 ¯1⎕MAP⍵;]}⍞

```

It first prompts for the file name, then for k. Note that a significant part of the running time (about 1 second) is just reading the file in.

To time it, you should be able to pipe the following into your `dyalog` executable (for the ten most frequent words):

```
⎕{m[⍺↑⍒⊢/m←{(⊂⎕UCS⊃⍺),≢⍵}⌸(⊢⊆⍨96∘<∧<∘123)83⎕DR 819⌶80 ¯1⎕MAP⍵;]}⍞
/tmp/ulysses64
10
⎕OFF

```

It should print:

```
 the  968832
 of   528960
 and  466432
 a    421184
 to   322624
 in   320512
 he   270528
 his  213120
 i    191808
 s    182144

```
> 3 votes

# Answer
# \[C\] Prefix Tree + Bins

***NOTE: The compiler used has a significant effect on program execution speed!*** I have used gcc (MinGW.org GCC-8.2.0-3) 8.2.0. When using the ***-Ofast*** switch, the program runs almost 50% faster than the normally compiled program.

**Algorithm Complexity**

I have since come to realise that the Bin sorting I am performing is a form of Pigeonhost sort this means that i can derrive the Big O complexity of this solution.

I calculate it to be:

```
Worst Time complexity: O(1 + N + k)
Worst Space complexity: O(26*M + N + n) = O(M + N + n)

Where N is the number of words of the data
and M is the number of letters of the data
and n is the range of pigeon holes
and k is the desired number of sorted words to return
and N<=M

```

The tree construction complexity is equivalent to tree traversal so since at any level the correct node to traverse to is O(1) (as each letter is mapped directly to a node and we are always only traverse one level of the tree for each letter)

Pigeon Hole sorting is O(N + n) where n is the range of key values, however for this problem, we do not need to sort all values, only the k number so the worst case would be O(N + k).

Combining together yields O(1 + N + k).

Space Complexity for tree construction is due to fact that the worst case is 26\*M nodes if the data consists of one word with M number of letters and that each node has 26 nodes (i.e. for the letters of the alphabet). Thus O (26\*M) = O(M)

For the Pigeon Hole sorting has space complexity of O(N + n)

Combining together yields O(26\*M + N + n) = O(M + N + n)

**Algorithm**

It takes two arguments as input (path to text file and for k number of most frequent words to list)

Based on my other entries, this version has a very small time cost ramp with increasing values of k compared to my other solutions. But is noticeably slower for low values of k however it should be much faster for larger values of k.

It create a tree branching on letters of words, then at the leaf letters it increments a counter. Then adds the word to a bin of words of the same size (after first removing the word from bin it already resided in). This all repeats until no more letters are read in. After which the bins are reverse iterated k times starting from the largest bin and the words of each bin are output.

It currently defaults to output the processing time, but for purposes of conistency with other submissions, disable the TIMING definition in the source code.

```
// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

// may need to increase if the source text has many repeated words
#define MAX_BINS 1000000

// assume maximum of 20 letters in a word... adjust accordingly
#define MAX_LETTERS_IN_A_WORD 20

// assume maximum of 10 letters for the string representation of the bin number... adjust accordingly
#define MAX_LETTERS_FOR_BIN_NAME 10

// maximum number of bytes of the output results
#define MAX_OUTPUT_SIZE 10000000

#define false 0
#define true 1
#define null 0
#define SPACE_ASCII_CODE 32

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    //char isAWord;
    struct Letter* parent;
    struct Letter* binElementNext;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

struct Bin
{
  struct Letter* word;
};
typedef struct Bin Bin;

int main(int argc, char *argv[])
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n\n");
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i, j;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], null, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the memory for bins
    Bin* bins = (Bin*) malloc(sizeof(Bin) * MAX_BINS);
    memset(&bins[0], null, sizeof( Bin) * MAX_BINS);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;
    Letter *nextFreeLetter = &letters[0];

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;

    // the next letter to be processed
    Letter* nextLetter = null;

    unsigned int sortedListSize = 0;

    // the count of the most frequent word
    unsigned int maxCount = 0;

    // the count of the current word
    unsigned int wordCount = 0;

////////////////////////////////////////////////////////////////////////////////////////////
// CREATING PREFIX TREE
    j=dataLength;
    while (--j>0)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                ++letterMasterIndex;
                nextLetter = ++nextFreeLetter;
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        else
        {
            //currentLetter->isAWord = true;

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////
// ADDING TO BINS

    j = letterMasterIndex;
    currentLetter=&letters[j-1];
    while (--j>0)
    {

      // is the letter the leaf letter of word?
      if (currentLetter->count>0)
      {
        i = currentLetter->count;
        if (maxCount < i) maxCount = i;

        // add to bin
        currentLetter->binElementNext = bins[i].word;
        bins[i].word = currentLetter;
      }
      --currentLetter;
    }

////////////////////////////////////////////////////////////////////////////////////////////
// PRINTING OUTPUT

    // the memory for output
    char* output = (char*) malloc(sizeof(char) * MAX_OUTPUT_SIZE);
    memset(&output[0], SPACE_ASCII_CODE, sizeof( char) * MAX_OUTPUT_SIZE);
    unsigned int outputIndex = 0;

    // string representation of the current bin number
    char binName[MAX_LETTERS_FOR_BIN_NAME];
    memset(&binName[0], SPACE_ASCII_CODE, MAX_LETTERS_FOR_BIN_NAME);

    Letter* letter;
    Letter* binElement;

    // starting at the bin representing the most frequent word(s) and then iterating backwards...
    for ( i=maxCount;i>0 && k>0;i--)
    {
      // check to ensure that the bin has at least one word
      if ((binElement = bins[i].word) != null)
      {
        // update the bin name
        sprintf(binName,"%u",i);

        // iterate of the words in the bin
        while (binElement !=null && k>0)
        {
          // stop if we have reached the desired number of outputed words
          if (k-- > 0)
          {
              letter = binElement;

              // add the bin name to the output
              memcpy(&output[outputIndex],&binName[0],MAX_LETTERS_FOR_BIN_NAME);
              outputIndex+=MAX_LETTERS_FOR_BIN_NAME;

              // construct string of letters to form the word
               while (letter != root)
              {
                // output the letter to the output
                output[outputIndex++] = letter->asciiCode+97;
                letter=letter->parent;
              }

              output[outputIndex++] = '\n';

              // go to the next word in the bin
              binElement = binElement->binElementNext;
          }
        }
      }
    }

    // write the output to std out
    fwrite(output, 1, outputIndex, stdout);
   // fflush(stdout);

   // free( data );
   // free( letters );
   // free( bins );
   // free( output );

#ifdef TIMING
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

```

EDIT: now deferring populating bins until after tree is constructed and optimising construction of output.

EDIT2: now using pointer arithmetic instead of array access for speed optimisation.
> 3 votes

# Answer
#

```
9!:37 ] 0 _ _ _

'input k' =: _2 {. ARGV
k =: ". k

lower =: a. {~ 97 + i. 26
words =: ((lower , ' ') {~ lower i. ]) (32&OR)&.(a.&i.) fread input
words =: ' ' , words
words =: -.&(s: a:) s: words
uniq =: ~. words
res =: (k <. # uniq) {. \:~ (# , {.)/.~ uniq&i. words
echo@(,&": ' ' , [: }.@": {&uniq)/"1 res

exit 0

```

Run as a script with `jconsole <script> <input> <k>`. For example, the output from the `giganovel` with `k=100K`:

```
$ time jconsole solve.ijs giganovel 100000 | head
11309 e
11290 ihit
11285 ah
11260 ist
11255 aa
11202 aiv
11201 al
11188 an
11187 o
11186 ansa

real    0m13.765s
user    0m11.872s
sys     0m1.786s

```

There's no limit except for the amount of available system memory.
> 3 votes

# Answer
# Java

I though it would be nice to get Java represented. There i nothing novel in the approach, just porting what others have done.

```
package trie;

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;

public class ByteTrie {

    static class Node {
        public Node parent;
        public int index;
        public Node[] nodes = null;
        public int count;

        public Node(Node parent, int index) {
            this.parent = parent;
            this.index = index;
            Trie.allNodes.add(this);
        }

        public String getWord() {
            if (this.index >= 0) {
                return this.parent.getWord() + (char) (this.index + 97);
            } else {
                return "";
            }
        }

        public Node traverse(int b) {
            if (this.nodes == null) {
                this.nodes = new Node[26];
                return this.nodes[b] = new Node(this, b);
            }
            if (this.nodes[b] == null) return this.nodes[b] = new Node(this, b);
            return this.nodes[b];
        }
    }

    static class Trie {
        public static List<Node> allNodes = new ArrayList<>();
        private final Node root = new Node(null, -1);
    }

    public static class App {
        private final String filename;
        private final int k;

        public App(String filename, int k) {
            this.filename = filename;
            this.k = k;
        }

        public void run() throws IOException {
            Trie trie = new Trie();

            Path path = Paths.get(filename);

            Node current = trie.root;

            InputStream inputStream = Files.newInputStream(path);
            BufferedInputStream bufferedInputStream = new BufferedInputStream(inputStream);
            int b;
            boolean inWord = false;
            while ((b = bufferedInputStream.read()) != -1) {
                int u = ((b | 32) - 97);
                if (u >= 26 || u < 0) {
                    if (inWord) {
                        ++current.count;
                    }
                    inWord = false;
                } else {
                    if (!inWord) {
                        current = trie.root;
                    }
                    inWord = true;
                    current = current.traverse(u);
                }
            }

            bufferedInputStream.close();
            inputStream.close();
            Trie.allNodes.sort((o1, o2) -> Integer.compare(o2.count, o1.count));
            List<Node> finalList = Trie.allNodes.subList(0, k);
            for (Node node : finalList) {
                System.out.println(node.getWord() + "\t" + node.count);
            }
        }

    }

    public static void main(String[] args) throws IOException {
        if (args.length == 0) {
            System.out.println("Filename required");
            System.exit(1);
        }
        String filename = args[0];
        int k = args.length > 1 ? Integer.parseInt(args[1]) : 10;
        App app = new App(filename, k);
        app.run();
    }

}

```

The fun part is compiling it to a native image using GraalVM with PGO (which unfortunately requires GraalVM Enterprise Edition) which roughly cuts the runtime in half.

java:

```
time java -jar build/libs/trie-1.0-all.jar ../giganovel 100000
8.02s user 0.27s system 101% cpu 8.186 total

java -jar build/libs/trie-1.0-all.jar ../ulysses64 10
0.82s user 0.03s system 111% cpu 0.763 total

```

native image:

```
time ./trie-1.0-all ../giganovel 100000
4.14s user 0.26s system 96% cpu 4.582 total

time ./trie-1.0-all ../ulysses64 10
0.35s user 0.02s system 99% cpu 0.366 total

```

Full solution at https://github.com/dillon-sellars/MultiTrie
> 3 votes

# Answer
**RUST Hashmap with FNV hasher**

Managed to get around ~95% of the top performer's performance without a custom data structure by just using a good hashmap.

EDIT: This doesn't scale well to giganovel - which it is performing much worse on (2-3 times slower).

```
❯ time "./target/release/current ulysses64.txt 10"
Benchmark #1: ./target/release/current ulysses64.txt 10
  Time (mean ± σ):     718.8 ms ±  26.8 ms    [User: 643.0 ms, System: 66.2 ms]
  Range (min … max):   676.5 ms … 763.6 ms    10 runs

❯ time "./target/release/mine ulysses64.txt 10"
Benchmark #1: ./target/release/mine
  Time (mean ± σ):     760.8 ms ±  26.7 ms    [User: 660.5 ms, System: 90.0 ms]
  Range (min … max):   730.0 ms … 800.2 ms    10 runs

```

in cargo.toml:

```
[dependencies]
fnv = "1.0"

```

Code:

<pre><code>use std::env::args;
use std::fs::File;
use std::io::Read;
use std::str::from_utf8_unchecked;

use fnv::FnvHashMap;

type Result<T> = std::result::Result<T, Box<dyn std::error::Error>>;

struct WordServer<'a> {
    data: &'a [u8],
    index: usize,
}

impl<'a> Iterator for WordServer<'a> {
    type Item = &'a [u8];

    fn next(&mut self) -> Option<Self::Item> {
        let start = self.index;

        let end = loop {
            let b = match self.data.get(self.index) {
                Some(b) => *b,
                None => return None,
            };

            match b {
                0..=25 => self.index += 1,
                _ => break self.index,
            }
        };

        loop {
            let b = match self.data.get(self.index) {
                Some(b) => *b,
                None => return None,
            };

            match b {
                0..=25 => break,
                _ => self.index += 1,
            }
        }

        Some(&self.data[start..end])
    }
}

fn go(file: &str, topn: usize) -> Result<()> {
    let mut file = File::open(file)?;
    let file_len = file.metadata()?.len();

    let mut data = Vec::with_capacity(file_len as usize);

    file.read_to_end(&mut data)?;

    // Convert all data into lowercase and nulls
    let data = data
        .iter()
        .map(|b| (b | 0b100000).wrapping_sub(b'a'))
        .collect::<Vec<_>>();

    let word_server = WordServer {
        data: data.as_slice(),
        index: 0,
    };

    let cap = file_len >> 35;

    // let mut collection: HashMap<&[u8], u32> = HashMap::with_capacity(cap as usize);
    // let mut collection: HashMap<&[u8], u32> = HashMap::with_hasher();
    let mut collection = FnvHashMap::with_capacity_and_hasher(cap as usize, Default::default());

    // Add words to our collection

    for word in word_server {
        match collection.get_mut(word) {
            Some(num) => *num += 1,
            None => {
                collection.insert(word, 1);
            }
        }
    }

    // Now get top n words

    let mut all = collection.iter().collect::<Vec<(&&[u8], &u32)>>();

    all.sort_unstable_by(|a, b| b.1.partial_cmp(a.1).unwrap());

    for (b, c) in all.iter().take(topn) {
        let changed = b.iter().map(|b| b + b'a').collect::<Vec<u8>>();

        let string = unsafe { from_utf8_unchecked(&changed) };
        println!("Count: {}: {}", c, string);
    }

    Ok(())
}

fn main() {
    let mut args = args();
    let file = args.nth(1).unwrap();
    let topn = args.next().unwrap().parse::<usize>().unwrap();
    go(&file, topn).unwrap()
}
```
</code></pre>
> 2 votes

# Answer
# Scala Simple Implementation (using mutable.Map)

```
  val map = scala.collection.mutable.Map.empty[String, Int]

  def wordsFromFile(filePath: String) = {
    val file = scala.io.Source.fromFile(filePath)

    val regex = "[a-z]+".r()

    file
      .getLines()
      .flatMap(line => (regex findAllIn line.toLowerCase))
      .foreach { word =>
        val v = map.getOrElse(word, 0)
        map.put(word, v + 1)
      }

    file.close()
  }

  def freq(filePath: String, k: Int) = {
    wordsFromFile(filePath)

    map.toSeq
      .sortBy(a => -a._2)
      .take(k)
  }

  val start = System.currentTimeMillis()
  freq("ulysses64", 10)
    .foreach {
      case (word, count) => println(s"$word\t$count")
    }
  val end = System.currentTimeMillis()
  println(s"Time taken: ${end - start} ms")

```

Result:

```
the 968832
of  528960
and 466432
a   421184
to  322624
in  320512
he  270528
his 213120
i   191808
s   182144
Time taken: 3973 ms

```
> 2 votes

# Answer
# OCaml

**Pre-requisites:**

1. Install Opam
2. `$ opam install core dune`

```
$ opam --version
2.0.6

$ ocamlc --version
4.10.0

$ dune --version
2.3.1

$ opam show -f version core
v0.13.0

```

**File: main.ml**

```
open Core;;
let () =
  let argv = Sys.get_argv () in
  match argv with
  | [| _prog_name; file_name; limit |] ->
    let limit = Int.of_string limit in
    assert (limit > 0);
    In_channel.with_file file_name ~f:(fun in_ch -> (
      let word_counts = String.Table.create () in
      let update_word_counts current_chars =
        if not (List.is_empty current_chars) then (
          let current_word = String.of_char_list @@ List.rev current_chars in
          String.Table.update word_counts current_word
            ~f:(fun v -> 1 + (Option.value v ~default:0))) in
      let buf_size = 1048576 in
      let buf = Bytes.create buf_size in
      let finished = ref false in
      let current_chars = ref [] in
      while not !finished do
        let len = In_channel.input in_ch ~buf ~pos:0 ~len:buf_size in
        if len > 0 then (
          for i = 0 to (len - 1) do
            let ch = Caml.Bytes.get buf i in
            current_chars := (
              if Char.is_alpha ch then ((Char.lowercase ch) :: !current_chars)
              else (update_word_counts !current_chars; []))
          done
        ) else finished := true
      done;
      update_word_counts !current_chars;
      let count = Int.min limit (String.Table.length word_counts) in
      let max_word, max_count, max_wcs = ref "", ref 0, ref [] in
      for _i = 1 to count do
        String.Table.iteri word_counts ~f:(fun ~key ~data ->
          if data > !max_count then (max_word := key; max_count := data));
        String.Table.remove word_counts !max_word;
        max_wcs := (!max_word, !max_count) :: (!max_wcs);
        max_word := ""; max_count := 0
      done;
      max_wcs := List.sort (!max_wcs) ~compare:(fun (w1, c1) (w2, c2) ->
        if phys_equal c1 c2 then String.compare w1 w2 else Int.compare c2 c1);
      List.iter (!max_wcs) ~f:(fun (word, count) ->
        Printf.printf "%s %d\n" word count)))
  | _ -> Printf.eprintf "Error: Usage: %s file-name limit\n" argv.(0)

```

**File: dune**

```
(executable
 (name main)
 (libraries core))

```

**Build:**

```
$ dune build main.exe

```

**Run:**

```
$ time ./_build/default/main.exe ulysses64 10
the 968832
of 528960
and 466432
a 421184
to 322624
in 320512
he 270528
his 213120
i 191808
s 182144

real  0m6.143s
user  0m6.047s
sys   0m0.068s

```
> 2 votes

# Answer
Since only latin words are searched for, don't forget to export LC\_ALL=C:

```
$ time ./wordcount.sh /tmp/ulysses64.txt 10
...
./wordcount.sh /tmp/ulysses64.txt 10  31.48s user 0.63s system 103% cpu 31.016 total
$ time ./wordcount.mawk /tmp/ulysses64.txt 10
...
./wordcount.mawk /tmp/ulysses64.txt 10  3.68s user 0.14s system 104% cpu 3.653 total
$ export LC_ALL=C
$ time ./wordcount.sh /tmp/ulysses64.txt 10
...
./wordcount.sh /tmp/ulysses64.txt 10  8.64s user 0.42s system 113% cpu 7.979 total
$ time ./wordcount.mawk /tmp/ulysses64.txt 10
...
./wordcount.mawk /tmp/ulysses64.txt 10  3.58s user 0.12s system 104% cpu 3.541 total

```

wordcount.sh:

```
#!/bin/sh
tr -cs A-Za-z '\n' <"$1" | tr A-Z a-z | sort | uniq -c | sort -rn | head -n"$2"

```

wordcount.mawk:

```
#!/bin/sh
tr A-Z a-z <"$1" | mawk -vRS='[^a-z]+' '
    {++count[$0]}
    END {for (w in count) print count[w], w}' | \
        sort -k1,1 -rn | head -n"$2"

```

By the way, here's a simpler and faster wordcount.py:

```
#!/usr/bin/env python3.9
import collections, re, sys

filename = sys.argv[1]
k = int(sys.argv[2])
reg = re.compile('[a-z]+')

counts = collections.Counter()
counts.update(reg.findall(open(filename).read().lower()))
for i, w in counts.most_common(k):
    print(i, w)

```

Result:

```
$ time ./wordcount_SE.py /tmp/ulysses64.txt 10
...
./wordcount_SE.py /tmp/ulysses64.txt 10  16.28s user 0.22s system 99% cpu 16.508 total
$ time ./wordcount.py /tmp/ulysses64.txt 10
...
./wordcount.py /tmp/ulysses64.txt 10  10.65s user 0.96s system 99% cpu 11.607 total

```

My favourite scripting language is quite slow, sadly:

```
$ time ./wordcount.tcl /tmp/ulysses64.txt 10
...
./wordcount.tcl /tmp/ulysses64.txt 10  24.13s user 0.87s system 99% cpu 25.000 total

```

wordcount.tcl:

```
#!/usr/bin/env tclsh

proc wordcount {path head} {
    set data [string tolower [read [open $path]]]
    foreach word [regexp -all -inline {[a-z]+} $data] {
        dict incr wordcount $word
    }
    set sorted [lsort -stride 2 -index 1 -int -decr $wordcount]
    lrange $sorted 0 [expr {$head * 2 - 1}]
}

foreach {count word} [wordcount {*}$argv] {
    puts "$word\t$count"
}

```

Everything done on Gentoo -O3 -march=native with an AMD 2700X, mawk-20200106, python 3.9, tcl-8.6.8 and coreutils 8.32.

PS: some interesting additions would be Pypy and LuaJIT
> 2 votes

# Answer
# \[C\] Prefix Tree + Sorted Linked List

It takes two arguments as input (path to text file and for k number of most frequent words to list)

Based on my other entry, this version is much faster for larger values of k but at a minor cost of performance at lower values of k.

It create a tree branching on letters of words, then at the leaf letters it increments a counter. Then checks to see if the current leaf counter is greater than the smallest most frequent word in the list of most frequent words. (list size is the number determined via the command line argument) If so then promote the word represented by the leaf letter to be one of the most frequent. If already a most frequent word, then swap with the next most frequent if the word count is now higher, thus keeping the list sorted. This all repeats until no more letters are read in. After which the list of most frequent words are output.

It currently defaults to output the processing time, but for purposes of conistency with other submissions, disable the TIMING definition in the source code.

```
// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

#define false 0
#define true 1
#define null 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    char isTopWord;
    struct Letter* parent;
    struct Letter* higher;
    struct Letter* lower;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

int main(int argc, char *argv[])
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n\n");
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], 0, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;

    // the next letter to be processed
    Letter* nextLetter = null;
    Letter* sortedWordsStart = null;
    Letter* sortedWordsEnd = null;
    Letter* A;
    Letter* B;
    Letter* C;
    Letter* D;

    unsigned int sortedListSize = 0;

    unsigned int lowestWordCount = 0;
    unsigned int lowestWordIndex = 0;
    unsigned int highestWordCount = 0;
    unsigned int highestWordIndex = 0;

    // main loop
    for (int j=0;j<dataLength;j++)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                nextLetter = &letters[letterMasterIndex++];
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        // not a letter so this means the current letter is the last letter of a word (if any letters)
        else if (currentLetter!=root)
        {

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // is this word not in the top word list?
            if (!currentLetter->isTopWord)
            {
                // first word becomes the sorted list
                if (sortedWordsStart == null)
                {
                  sortedWordsStart = currentLetter;
                  sortedWordsEnd = currentLetter;
                  currentLetter->isTopWord = true;
                  ++sortedListSize;
                }
                // always add words until list is at desired size, or
                // swap the current word with the end of the sorted word list if current word count is larger
                else if (sortedListSize < k || currentLetter->count> sortedWordsEnd->count)
                {
                    // replace sortedWordsEnd entry with current word
                    if (sortedListSize == k)
                    {
                      currentLetter->higher = sortedWordsEnd->higher;
                      currentLetter->higher->lower = currentLetter;
                      sortedWordsEnd->isTopWord = false;
                    }
                    // add current word to the sorted list as the sortedWordsEnd entry
                    else
                    {
                      ++sortedListSize;
                      sortedWordsEnd->lower = currentLetter;
                      currentLetter->higher = sortedWordsEnd;
                    }

                    currentLetter->lower = null;
                    sortedWordsEnd = currentLetter;
                    currentLetter->isTopWord = true;
                }
            }
            // word is in top list
            else
            {
                // check to see whether the current word count is greater than the supposedly next highest word in the list
                // we ignore the word that is sortedWordsStart (i.e. most frequent)
                while (currentLetter != sortedWordsStart && currentLetter->count> currentLetter->higher->count)
                {
                    B = currentLetter->higher;
                    C = currentLetter;
                    A = B != null ? currentLetter->higher->higher : null;
                    D = currentLetter->lower;

                    if (A !=null) A->lower = C;
                    if (D !=null) D->higher = B;
                    B->higher = C;
                    C->higher = A;
                    B->lower = D;
                    C->lower = B;

                    if (B == sortedWordsStart)
                    {
                      sortedWordsStart = C;
                    }

                    if (C == sortedWordsEnd)
                    {
                      sortedWordsEnd = B;
                    }
                }
            }

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

    // print out the top frequent words and counts
    char string[256];
    char tmp[256];

    Letter* letter;
    while (sortedWordsStart != null )
    {
        letter = sortedWordsStart;
        highestWordCount = letter->count;
        string[0]=0;
        tmp[0]=0;

        if (highestWordCount > 0)
        {
            // construct string of letters to form the word
            while (letter != root)
            {
                memmove(&tmp[1],&string[0],255);
                tmp[0]=letter->asciiCode+97;
                memmove(&string[0],&tmp[0],255);
                letter=letter->parent;
            }

            printf("%u %s\n",highestWordCount,string);
        }
        sortedWordsStart = sortedWordsStart->lower;
    }

    free( data );
    free( letters );

#ifdef TIMING
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

```
> 1 votes

# Answer
# Python 3

This implementation with a simple dictionary is slightly faster than the one using `Counter` one on my system.

```
def words_from_file(filename):
    import re

    pattern = re.compile('[a-z]+')

    for line in open(filename):
        yield from pattern.findall(line.lower())

def freq(textfile, k):
    frequencies = {}

    for word in words_from_file(textfile):
        frequencies[word] = frequencies.get(word, 0) + 1

    most_frequent = sorted(frequencies.items(), key=lambda item: item[1], reverse=True)

    for i, (word, frequency) in enumerate(most_frequent):
        if i == k:
            break

        yield word, frequency

from time import time

start = time()
print('\n'.join('{}:\t{}'.format(f, w) for w,f in freq('giganovel', 10)))
end = time()
print(end - start)

```
> 1 votes

# Answer
# C#

This one should work with the lastest .net SDKs.

```
using System;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Node {
    public Node Parent;
    public Node[] Nodes;
    public int Index;
    public int Count;

    public static readonly List<Node> AllNodes = new List<Node>();

    public Node(Node parent, int index) {
        this.Parent = parent;
        this.Index = index;
        AllNodes.Add(this);
    }

    public Node Traverse(uint u) {
        int b = (int)u;
        if (this.Nodes is null) {
            this.Nodes = new Node[26];
            return this.Nodes[b] = new Node(this, b);
        }
        if (this.Nodes[b] is null) return this.Nodes[b] = new Node(this, b);
        return this.Nodes[b];
    }

    public string GetWord() => this.Index >= 0
        ? this.Parent.GetWord() + (char)(this.Index + 97)
        : "";
}

class Freq {
    const int DefaultBufferSize = 0x10000;

    public static void Main(string[] args) {
        var sw = Stopwatch.StartNew();

        if (args.Length < 2) {
            WriteLine("Usage: freq.exe {filename} {k} [{buffersize}]");
            return;
        }

        string file = args[0];
        int k = int.Parse(args[1]);
        int bufferSize = args.Length >= 3 ? int.Parse(args[2]) : DefaultBufferSize;

        Node root = new Node(null, -1) { Nodes = new Node[26] }, current = root;
        int b;
        uint u;

        using (var fr = new FileStream(file, FileMode.Open))
        using (var br = new BufferedStream(fr, bufferSize)) {
            outword:
                b = br.ReadByte() | 32;
                if ((u = (uint)(b - 97)) >= 26) {
                    if (b == -1) goto done;
                    else goto outword;
                }
                else current = root.Traverse(u);
            inword:
                b = br.ReadByte() | 32;
                if ((u = (uint)(b - 97)) >= 26) {
                    if (b == -1) goto done;
                    ++current.Count;
                    goto outword;
                }
                else {
                    current = current.Traverse(u);
                    goto inword;
                }
            done:;
        }

        WriteLine(string.Join("\n", Node.AllNodes
            .OrderByDescending(count => count.Count)
            .Take(k)
            .Select(node => node.GetWord())));

        WriteLine("Self-measured milliseconds: {0}", sw.ElapsedMilliseconds);
    }
}

```

Here's a sample output.

```
C:\dev\freq>csc -o -nologo freq-trie.cs && freq-trie.exe giganovel 100000
e
ihit
ah
ist
 [... omitted for sanity ...]
omaah
aanhele
okaistai
akaanio
Self-measured milliseconds: 13619

```

At first, I tried to use a dictionary with string keys, but that was way too slow. I think it's because .net strings are internally represented with a 2-byte encoding, which is kind of wasteful for this application. So then I just switched to pure bytes, and an ugly goto-style state machine. Case conversion is a bitwise operator. Character range checking is done in a single comparison after subtraction. I didn't spend any effort optimizing the final sort since I found it's using less than 0.1% of the runtime.

Fix: The algorithm was essentially correct, but it was over-reporting total words, by counting all prefixes of words. Since total word count isn't a requirement of the problem, I removed that output. In order to output all k words, I also adjusted the output. I eventually settled on using `string.Join()` and then writing the whole list at once. Surprisingly this is about a second faster on my machine that writing each word separately for 100k.
> 1 votes

# Answer
# Ruby 2.7.0-preview1 with `tally`

The latest version of Ruby has a new method called `tally`. From the release notes:

> `Enumerable#tally` is added. It counts the occurrence of each element.

```
["a", "b", "c", "b"].tally
#=> {"a"=>1, "b"=>2, "c"=>1}

```

This almost solves the entire task for us. We just need to read the file first and find the max later.

Here's the whole thing:

```
k = ARGV.shift.to_i

pp ARGF
  .each_line
  .lazy
  .flat_map { @1.scan(/[A-Za-z]+/).map(&:downcase) }
  .tally
  .max_by(k, &:last)

```

*edit: Added `k` as an command line argument*

It can be run with `ruby k filename.rb input.txt` using the 2.7.0-preview1 version of Ruby. This can be downloaded from various links on release notes page, or installed with rbenv using `rbenv install 2.7.0-dev`.

Example run on my own beat-up, old computer:

```
$ time ruby bentley.rb 10 ulysses64
[["the", 968832],
 ["of", 528960],
 ["and", 466432],
 ["a", 421184],
 ["to", 322624],
 ["in", 320512],
 ["he", 270528],
 ["his", 213120],
 ["i", 191808],
 ["s", 182144]]

real    0m17.884s
user    0m17.720s
sys 0m0.142s

```
> 1 votes

# Answer
## AWK + sort

Just for the sake of completeness, here are two solutions that work best for different versions of AWK.

This one works best with Michael Brennan's AWK (both `mawk-2` and `mawk 1.3.4`). It outperforms GNU awk by a factor of x7.5.

```
mawk -v RS="[^A-Za-z]+" '
{
    freq[tolower($0)]++;
}
END {
    for (word in freq)
        print(freq[word] " " word)
}
' filename | sort -rn | head -10

```

This version works best for the "one true awk" (`nawk`) and GNU awk (`gawk`).

```
awk -v FS="[^a-zA-Z]+" '
{
    for (i=1; i<=NF; i++)
        freq[tolower($i)]++;
}
END {
    for (word in freq)
        print(freq[word] " " word)
}
' filename | sort -rn | head -10

```

P.S. Bounty to anyone, who can find even faster AWK solution.
> 1 votes

---
Tags: fastest-code
---


# Question
Title: Implement constant-latency branchless multiplication efficiently
Modern hardware can perform multiplication very fast in a constant latency of 3~4 cycles. But some tiny chips for embedded environments sometimes lack hardware multiplication, which has to be emulated by a series of instructions.

### Goal

You are given a primitive CPU with a set of basic operations. Your job is to implement unsigned multiplication of two 8-bit numbers, each in register `c` and `d`, after which the result will be stored in registers `a` and `b`, `a` storing the lower bits and `b` storing the higher bits. You don't have to preserve the input in `c` and `d`.

### Spec

The machine has 26 8-bit registers from `a` to `z`, whose initial value is `0`. You are allowed to use all of them freely to implement this operation.

There are no "jumps" or branching instructions, but there are flags conditionally set according to the last operation.

* ZF : zero flag; set if the result is zero
* CF : carry flag; set if the result is "wrapped" for addition/subtraction; set if a bit was "carried out" for shift/rotation

There is no memory access.

### Score

The total sum of latency cycles plus the number of registers used will be your score, the lower the better.

### Available Instructions

`instr r0 r1/imm (2)` means `instr` takes two register operands, of which the second one can be an 8-bit immediate operand, and this instruction takes 2 cycles to complete.

All operations except `mov`, `swp`, `setX`, and `mskX` sets the zero flag accordingly.

* `mov r0 r1/imm (1)` : `r0 = r1`
* `swp r0 r1 (2)` : `r0 = r1`, `r1 = r0`
* `sswp r0 (2)` : swap the low 4 bits and the high 4 bits
* `setz/setnz/setc/setnc r0 (1)` : set `r0` to `1` if the specified flag was set, and `0` otherwise ; `z -> ZF, nz -> not ZF, c -> CF, nc -> not CF`
* `mskz/msknz/mskc/msknc r0 (1)` : set `r0` to `0xff` if the specified flag was set, and `0` otherwise
* `add r0 r1/imm (2)` : `r0 = r0 + r1`; CF affected
* `sub r0 r1/imm (2)` : `r0 = r0 - r1`; CF affected
* `adc r0 r1/imm (3)` : `r0 = r0 + r1 + CF`; CF affected
* `sbb r0 r1/imm (3)` : `r0 = r0 - r1 - CF`; CF affected
* `and r0 r1/imm (2)` : `r0 = r0 & r1`
* `or r0 r1/imm (2)` : `r0 = r0 | r1`
* `xor r0 r1/imm (2)` : `r0 = r0 ^ r1`
* `shr r0 (1)` : bitshift right once shifting in a zero; CF is the old least significant bit (LSB)
* `shl r0 (1)` : bitshift left once shifting in a zero; CF is the old most significant bit (MSB)
* `ror r0 (1)` : rotate right; bitshift right once shifting in the LSB; CF is the old LSB
* `rol r0 (1)` : rotate left; bitshift left once shifting in the MSB; CF is the old MSB
* `rcr r0 (2)` : rotate right with carry; bitshift right once shifting in the CF; the new CF is the old LSB
* `rcl r0 (2)` : rotate left with carry; bitshift left once shifting in the CF; the new CF is the old MSB
* `not r0 (2)` : bitwise not
* `neg r0 (2)` : two's complement negation; same as `not r0; add r0 1`; `CF = not ZF`

---

Here, you can test your code that is translated to x86 assembly. Write your code below the label `mulb:`. I also added a working implementation ported from the work of @l4m2.

The tester has some limitations, though. It only supports 15 registers from `a` to `o`, and you have to write `shr a, 1` instead of `shr a` etc. because of NASM syntax.

This is a scoring program written by @tsh. It is also a full featured tester. I'd like to explain how to use it if I know Javascript, but unfortunately I don't. Feel free to edit this post if you can add an explanation.

# Answer
> 2 votes
# ~~87~~ ~~82~~ 80, destroying `c`

```
shl c
mskc a
and a, d

shl a
rcl c
mskc e
and e, d
add a, e
setc b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

add b, c

```

82 preserving `c` is trivial from 80 destroying it

Didn't notice that mul from most significant is faster

# 104

```
1 reg a # output low
1 reg b # output high
1 reg c # input
1 reg d # input
1 reg e # cur
1 reg f # back
0 # bit 0
1 ror d
1 msk a, C # mskc a by OP
2 and a, c
1 mov b, a
0 # bit 1
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 254
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 252
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 248
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 240
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 224
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 192
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 128
2 add a, e
3 adc b, f
0 # fix b
2 sub b, a

```

Writing `set a, C` feel better and align friendly than `setc a`

# Answer
> 2 votes
# Score: ~~94~~ 92

Reduced score by 1 thanks to @xiver77.

```
rol c
mskc a
and a, d
shl a
setc b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0

```

Explanation:

```
rol c
mskc a
and a, d

```

Multiply the MSB of `c` by `d`.

```
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0

```

For each of the remaining seven bits, double `ba` and add `d` multiplied by the bit (`setc b` is used instead of `rcl b` for the first bit since it scores 1 fewer).

---
Tags: code-challenge, optimization, assembly
---