Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Challenge for Feeb: dealing with large numbers in C
Date: Thu, 24 Oct 2019 18:06:24 -0700
Organization: A noiseless patient Spider
Lines: 41
Message-ID: <86sgnhfxbj.fsf@linuxsc.com>
References: <e_4rF.285583$iJ2.198603@fx47.iad> <ld2qqedn61hgi25fa0602tle88oobhmspf@4ax.com> <Yq9rF.26213$kV2.22694@fx22.iad> <3pkrF.1790269$HWr.573547@fx36.am4> <CdnrF.146403$hL1.58740@fx35.iad> <K7IrF.3053334$dw4.575231@fx12.am4> <zB_rF.60706$VU2.40054@fx12.iad> <87y2xbvuzb.fsf@bsb.me.uk> <s3fsF.1855772$HWr.1014722@fx36.am4> <877e4uvstq.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="294289d8fb0afb0e43f75d31b2b6cc13"; logging-data="22943"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/maMrnsXBs4622cGol5337L5mfw/iB57c="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:garUwFDK2k9HPFCDOQx5nXaexGE= sha1:8XVukWizCPoJbMWzMIR+0RC0zHQ=
Xref: csiph.com comp.lang.c:147221

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> [..determining anagrams via letter counts comparison..]

I have a variation on the comparing-letter-counts approach
that some people may find interesting.

Some preliminaries:  one, I assume the word list has been
pre-binned by length, so only words of the same length
will be tested;  and two, there is an array for converting
character codes to indices in the counts arrays (with any
non-letters having an out-of-range index value).

Here is the code (disclaimer: not tested):

#define ALPHABET_SIZE   26

static unsigned char *const letter_map;    /* character value => index */

int
is_anagram_of( const char *s, unsigned char counts[ static ALPHABET_SIZE ] ){
    unsigned char h[ ALPHABET_SIZE ] = { 0 };

    for(  int c = *s;  c;  c = *++s  ){
        unsigned k = letter_map[c];
        if(  k >= ALPHABET_SIZE  ||  ++h[k] > counts[k]  )  return  0;
    }

    return  1;
}

The checking goes through the test string, s, incrementing counts
as it goes.  If any character is encountered (a) that is not a
letter (so its index is out of range), or (b) whose count exceeds
that of the corresponding letter of the word being tested against,
the test string cannot be an anagram of the pre-counted word, so
zero is returned immediately.

If the loop completes, we know no counts have been exceeded, and
we know the lengths match, so the only remaining possibility is
that all the counts match.  Voila!  That's an anagram.