Last letter-first letter: Difference between revisions
Content added Content deleted
(Fixed bug in second D version) |
(Added C version) |
||
Line 22: | Line 22: | ||
Extra brownie points for dealing with the full list of 646 names. |
Extra brownie points for dealing with the full list of 646 names. |
||
=={{header|C}}== |
|||
From the D version. |
|||
<lang c>#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <stdio.h> |
|||
#include <inttypes.h> |
|||
typedef struct { |
|||
uint16_t index; |
|||
unsigned char last_char, first_char; |
|||
} Ref; |
|||
Ref* longest_path_refs; |
|||
size_t longest_path_refs_len; |
|||
Ref* refs; |
|||
size_t refs_len; |
|||
size_t n_solutions; |
|||
char** longest_path; |
|||
size_t longest_path_len; |
|||
/// tally statistics |
|||
void search(const size_t curr_len) { |
|||
if (curr_len == longest_path_refs_len) { |
|||
n_solutions++; |
|||
} else if (curr_len > longest_path_refs_len) { |
|||
n_solutions = 1; |
|||
longest_path_refs_len = curr_len; |
|||
memcpy(longest_path_refs, refs, curr_len * sizeof(Ref)); |
|||
} |
|||
// recursive search |
|||
const size_t last_char = refs[curr_len - 1].last_char; |
|||
for (size_t i = curr_len; i < refs_len; i++) |
|||
if (refs[i].first_char == last_char) { |
|||
const Ref aux = refs[curr_len]; |
|||
refs[curr_len] = refs[i]; |
|||
refs[i] = aux; |
|||
search(curr_len + 1); |
|||
refs[i] = refs[curr_len]; |
|||
refs[curr_len] = aux; |
|||
} |
|||
} |
|||
void find_longest_chain(char** items, |
|||
const size_t items_len) { |
|||
refs_len = items_len; |
|||
refs = calloc(refs_len, sizeof(Ref)); |
|||
// enough space for all items |
|||
longest_path_refs_len = 0; |
|||
longest_path_refs = calloc(refs_len, sizeof(Ref)); |
|||
for (size_t i = 0; i < items_len; i++) { |
|||
const size_t itemsi_len = strlen(items[i]); |
|||
if (itemsi_len <= 1) |
|||
exit(1); |
|||
refs[i].index = (uint16_t)i; |
|||
refs[i].last_char = items[i][itemsi_len - 1]; |
|||
refs[i].first_char = items[i][0]; |
|||
} |
|||
// try each item as possible start |
|||
for (size_t i = 0; i < items_len; i++) { |
|||
const Ref aux = refs[0]; |
|||
refs[0] = refs[i]; |
|||
refs[i] = aux; |
|||
search(1); |
|||
refs[i] = refs[0]; |
|||
refs[0] = aux; |
|||
} |
|||
longest_path_len = longest_path_refs_len; |
|||
longest_path = calloc(longest_path_len, sizeof(char*)); |
|||
for (size_t i = 0; i < longest_path_len; i++) |
|||
longest_path[i] = items[longest_path_refs[i].index]; |
|||
free(longest_path_refs); |
|||
free(refs); |
|||
} |
|||
int main() { |
|||
char* pokemon[] = {"audino", "bagon", "baltoy", "banette", |
|||
"bidoof", "braviary", "bronzor", "carracosta", "charmeleon", |
|||
"cresselia", "croagunk", "darmanitan", "deino", "emboar", |
|||
"emolga", "exeggcute", "gabite", "girafarig", "gulpin", |
|||
"haxorus", "heatmor", "heatran", "ivysaur", "jellicent", |
|||
"jumpluff", "kangaskhan", "kricketune", "landorus", "ledyba", |
|||
"loudred", "lumineon", "lunatone", "machamp", "magnezone", |
|||
"mamoswine", "nosepass", "petilil", "pidgeotto", "pikachu", |
|||
"pinsir", "poliwrath", "poochyena", "porygon2", "porygonz", |
|||
"registeel", "relicanth", "remoraid", "rufflet", "sableye", |
|||
"scolipede", "scrafty", "seaking", "sealeo", "silcoon", |
|||
"simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga", |
|||
"trapinch", "treecko", "tyrogue", "vigoroth", "vulpix", |
|||
"wailord", "wartortle", "whismur", "wingull", "yamask"}; |
|||
const size_t pokemon_len = 70; |
|||
find_longest_chain(pokemon, pokemon_len); |
|||
printf("Maximum path length: %u\n", longest_path_len); |
|||
printf("Paths of that length: %u\n", n_solutions); |
|||
printf("Example path of that length:\n"); |
|||
for (size_t i = 0; i < longest_path_len; i += 7) { |
|||
printf(" "); |
|||
for (size_t j = i; j < (i+7) && j < longest_path_len; j++) |
|||
printf("%s ", longest_path[j]); |
|||
printf("\n"); |
|||
} |
|||
free(longest_path); |
|||
return 0; |
|||
}</lang> |
|||
Output: |
|||
<pre>Maximum path length: 23 |
|||
Paths of that length: 1248 |
|||
Example path of that length: |
|||
machamp petilil landorus scrafty yamask kricketune emboar |
|||
registeel loudred darmanitan nosepass simisear relicanth heatmor |
|||
rufflet trapinch haxorus seaking girafarig gabite exeggcute |
|||
emolga audino</pre> |
|||
Runtime: about 0.49 seconds, gcc compiler. |
|||
=={{header|D}}== |
=={{header|D}}== |