Recreate the sentence

Question

This challenge consists of two parts. The winner will be the solution with the lowest total byte count. The same language must be used for both challenges.

Part 1:

Write a function or program that takes a sentence with only valid words as input, and outputs a list of the used characters, the number of times each letter is used, and the number of letters in each of the words in the original sentence. The output from this program must be valid input to the next program (exactly as it is outputted)

I'll add examples and detailed rules further down.

Part 2:

Write a function or program that takes the output from the first program as input and uses this list of English words and recreates a sentence with the information from the output. The sentence doesn't have to be the same as the original sentence.

More information. rules and restrictions:

Part 1:

• The first input can be on any suitable format, with or without quotation marks, as function argument or from STDIN, with or without brackets etc.
• The input sentence will not contain any punctuation or special characters, except for a period/dot in the end. Except for the period symbol, all characters that are in the input will be in the word list.
• The first letter of the sentence will be upper case, the rest will be lower case.
• The output of part 2 must start with the same upper case letter as the original sentence (so converting the input to lower case is not recommended (but OK).
• The output can be on any suitable format:
  • It must be possible to copy-paste the output directly into the next program / function
  • No alterations can be made when copy-pasting, the entire output must be copied and pasted as a whole, not in parts.
  • You may for instance output a histogram of all letters in the alphabet, or only the ones used (in general, whatever is necessary to complete part 2)
  • You can not output a list of characters where multiple occurrences are repeated. For instance, The queue can't yield an output: Teeehquu (3,5), it should be something like: Tehqu, (1 3 1 1 2),(3 5).

Part 2:

• The program / function must accept the input exactly as is from part 1 (one exception, see comment below about taking file name as input.).
  • If surrounding brackets, quotation marks or similar are necessary to parse the input then these must be part of the output from part 1.
• The word list can be found here.
  • The word list can either be saved locally as w.txt, or it can be fetched from the url. The url will only count as 5 bytes, so you don't need a url-shortener.
  • If the program can't open a file without reading the name as an input from STDIN (I believe this is was the case for Pyth at least), then the file name can be taken as a separate input argument.
• The output must be only a sentence (list of valid words), ending with a period and an optional newline.
  • The output must have words with the same number of letters as the original sentence in part 1 (in correct order)
  • All the letters that were used in the original sentence must be used in the new output.
  • The sentence must start with the same upper case letter as the original input sentence and end with a period.

Both parts:

• Neither of the parts should take more than 2 minutes to execute (randomly picking out words until a solution is reached is not accepted).

With the rules listed above, there should be a fair chance that the exact same sentence is reproduced, however that is not a requirement.

Examples:

In the below examples, a few different input and output formats are shown. Many more are accepted.

Part 1:

Input:

Zulus win.

Output type 1:

Z i l n s u w
1 1 1 1 1 2 1
5 3

Output type 2:

(('Z',1),('i',1),('l',1),('n',1),('s',1),('u',2),('w',1)), (5,2)

Output type 3:

'Zilnsuuw',[1,1,1,1,1,2,1],[5,2]

Part 2:

Input: An exact copy of the output from part 1. Output:

Zulus win.

Note that other word combinations are accepted as long as they start with a Z, and the first word has 5 letters and the second has 3.

The shortest code in bytes win.

Answer 1

LabVIEW, 166 LabVIEW Primitives

First of all i did not create 2 seperate programms because Labview does dataflow so theres really no need.

Saves the histogramm with first element = ascii code of first letter rest from 1-26 go by amount. Lenght simply gets saved in an array.

The first word has 3 checks, first letter, lenght and available letters in histogram. The first letter check stops after the first word.

I check the histogram by decrementing it for every letter and checking if it would fall below 0.

If i found my Nth word and there are no words that are buildable from the left over letters i will start deleting words from the dictonary and redo the Nth word and so on until i have found a solution.

This might or might not work for sentences there are, since that would take forever to compute (my example took a few seconds already).

What i tried

In: Zulus win.
Out: Zulus win.

In: Dovecot flagships oleander.
Out: Dolphin advocates forelegs.

In: Abash abel mammal test.
Out: Amass abbe hamlet malt.

Answer 2

Python 2.7, 353 bytes

Unfortunately, I can't test it with the actual w.txt file ATM because QPython for Android can't seem to handle file I/O. It worked with data I copied and pasted though.

Part 1, 76 bytes

h=lambda s:({c:s.count(c)for c in s if c.isalnum()},map(len,s[:-1].split()))

In: 'Hi there.'

Out: {'H':1, 'i':1, 't':1, 'h':1, 'e':2, 'r':1}, (2, 5)

so, a list containing:

• a hashmap with the histogram

• a list of letter counts

Part 2, 277 bytes

import itertools as i
m=lambda c:' '.join([s for s in i.product(*[[w for w in open('w.txt')if len(w)==length]for length in c[1]])if sorted(''.join(s))==sorted(sum([[k.lower()]*n for k,n in c[0].items()],[]))and s[0][0]==filter(str.isupper,c[0])[0].lower()][0]).capitalize()+'.'

I'm really glad I managed to make it 100% pure functional. Not sure if that helps with the actual golfing, but I certainly got the obfuscation part right :D Here's A more human friendly version of pt. 2 (exactly the same flow, but with variable names):

from itertools import product

def matching(counts):
  histo, word_lengths = counts
  first_letter = filter(str.isupper, histo)[0].lower()
  
  letters_nested = [ [char.lower()]*count for char, count in histo.items() ]
  letters = sum(letters_nested, [])
  
  word_options = [[word for word in open('w.txt') if len(word)==length] for length in word_lengths]
  
  sentences = product(*word_options)
  
  valid = [sentence for sentence in sentences if sorted(''.join(sentence))==sorted(letters) and sentence[0][0]==first_letter]
  return ' '.join(valid[0]).capitalize()+'.'

Answer 3

Perl, 516 504 bytes

includes 2x +1 for -p

@l=map{length}/\w+/g;s/\w/$c{$&}++/eg;@h=map{"$_$c{$_}"}keys%c;$_="@h @l";chomp(@w=`cat w.txt`);s/([A-Z])1//;$o=$1;s/(\w)(\d)/$h{$1}=$2,''/eg;@L=/\d/g;$l=shift@L;@O=$_,s/^.//,g([@L],%h)&&last for grep{$l==length&&/^$o/i&&h(\%h,substr$_,1)}@w;$_="@O.";s/^./uc$&/e;sub g{my%g;($R,%g)=@_;my@R=@$R;if($j=shift@R){s/./$g{$&}--/eg;my@C=grep{$j==length&&h(\%g,$_)}@w;push(@O,$_),g([@R],%g)and return 1 or pop@O for@C;0}else{1}}sub h{($y,$z)=@_;my%T;$z=~s/\w/$T{$&}++/eg;$K=1;$K&=$T{$_}<=$y->{$_}for keys%T;$K}

Requires to have w.txt in unix format (\n line endings). Uses cat to read the file; change to type for windows.
Save the oneliner above in 534.pl and run as echo Test. | perl -p 534.pl.

Pretty large, but it's a start - lots of golfing opportunities, but I just wanted to post it to make the LabVIEW answer less lonely ;-). I've omitted the optimisations for sub-second execution, saving 30+ bytes.

---

First snippet (73 bytes):

@l=map{length}/\w+/g;s/\w/$c{$&}++/eg;@h=map{"$_$c{$_}"}keys%c;$_="@h @l"

It produces a histogram and the word lenghts in a compact format. For input Zulus win. it produces a type-2 output without the (,), which aren't necessary here:

s1 l1 u2 Z1 w1 i1 n1 5 3

Here it is, ungolfed:

sub i{
    $_=shift;                       # get parameter
    @l = map{length} /\w+/g;        # cound word lengths
    s/\w/$c{$&}++/eg;               # count letters in hash %c
    @h=map{"$_$c{$_}"}keys%c;       # construct letter-frequency pairs
    "@h @l"                         # implicit interpolation with $" (space) separator
}

Second snippet (441 bytes)

This main part deals with I/O and the special treatment of the first letter, using subroutines g and h that are listed below.

sub o {
    $_=shift;
    chomp(@w=`cat w.txt`);          # load the wordlist.

    s/([A-Z])1//; $o=$1;            # get and remove the uppercase character,
    s/(\w)(\d)/$h{$1}=$2,''/eg;     # reconstruct histogram in hash %h.
    @L=/\d/g;                       # get the word counts.

    $l = shift @L;                  # get the first word length.

    @O = $_,                        # initialize output with first word,
    s/^.//,                         # strip first char of word
    g([@L],%h) && last              # call the main algoritm and quit on success

    for grep {                      
            $l==length &&           # check length
            /^$o/i &&               # only match words starting with the uppercase char
            h(\%h,substr$_,1)       # check if the word satisfies the histogram
        } @w;                       # iterates all words (speedups removed).

    $_="@O.";                       # construct output sentence.
    s/^./uc$&/e;                    # make first char uppercase.
    $_
}

This recursive function takes a copy of the histogram, a copy of the remaining word counts, and the current word. If the word-length array is empty, returns true. Else it decrements the histogram count for the letters in the given word, takes the next word-length, and finds a list of suitable words from the wordlist. For each suitable word, it recurses.

sub g {
    my%g;                           # local version of histogram
    ($R,%g)=@_;                     # get parameters.
    my@R=@$R;                       # dereference arrayref copy of word lengths.

    if($j=shift @R)                 # get the next word-length.
    {
        s/./$g{$&}--/eg;            # update histogram

        my @C =                     # get a list of suitable words.
        grep { $j==length && h(\%g,$_) }
        @w;

        push(@O,$_),                # append word to output
        g( [@R], %g )               # recurse.
            and return 1            # true: append word we're done.
            or pop @O               # remove word from output
        for @C                      # (for some reason the @C=grep doesn't work here)

        ;0
    } else { 1 }                    # no more words, done!
}

And finally, this subroutine is given a word and the sentence histogram. It calculates a new histogram for the word and checks whether all letters do not occur more often than permitted by the sentence histogram.

# check if first histogram is within bounds of second
sub h{
    ($y,$z)=@_;
    my%T; $z =~ s/\w/$T{$&}++/eg;    # calc histogram

    $K=1;
    $K &= $T{$_} <= $y->{$_}
    for keys %T;#$_[0];
    $K
}

You can paste the ungolfed snippets (sub i/o/g/h) in a single file and append the below test code.

sub t {
    print $i=i(shift),$/,o($i),$/x2;
    %c=%h=@L=@X=@O=();
}

t "Test.";                              # Test.
t "Zulus win.";                         # Zulus win.
t "Happy solstice.";                    # Happy solstice.
t "Abash abel mammal test.";            # Abase alms embalm that.
t "Dovecot flagships oleander.";        # Dangled horoscope festival.
t 'This code requires further golfing.';# Tech deer fighting ferrous liquors.

---

• update 504: save 12 bytes eliminating a substr and a parameter for sub g.