Cod golf: condense your shoal
+5
−0
Your answer is a string containing 255 fishes as subsequences, and your score is the length of that string in bytes (lowest score wins).
Rules
- Your string must include at least 255 fishes from the list below as subsequences.
- More than 1 fish can share the same character.
- Each of your fishes must be exactly as it appears in the list:
- The spelling must be identical.
- Any spaces and punctuation must be identical.
There is no benefit (and also no penalty) if you include more than 255 fishes as subsequences. Provided you include at least 255, only the length of your string affects your score.
This is not code golf. The length of your code is irrelevant.
Examples
- Note that unlike substrings, subsequences do not have to be contiguous. For example,
codis a subsequence ofzzzcodzzz, andcodis also a subsequence ofzczozzzdz. Provided the characters of the fish are in the correct order, they can have arbitrarily many other characters in between. Equivalently, for a fish to count as a subsequence of your string, it must be possible to remove characters from your string until what remains is the name of the fish. - Since more than 1 fish can share some of the same characters,
zzzbanjo catfishzzzcontains 3 fishes:banjo,catfish, andbanjo catfisheven though some of the letters are used by more than 1 fish. - Each fish in the list below can only be counted once. So
zzzcatfishcatfishzzzcontainscatfishtwice, but it only counts as one fish. - The need for an exact match including spaces and punctuation means that
peters' elephantnose fishis valid, butpeter's elephantnose fish(apostrophe in the wrong place) andpeterselephantnosefish(missing spaces) are not. - Identical spelling includes maintaining regional spelling differences. Notice that the list contains
armored searobinandarmoured catfish, notarmoured searobinandarmored catfish.
Answer format
The automated leaderboard will include your answer provided you use the correct answer format:
## Language name, 9876
Optional arbitrary text.
```
code used to produce the competing string
```
Optional arbitrary text.
```txt
code block containing your competing string
```
Optional arbitrary text.
Putting your competing string in a code block keeps it on one line rather than wrapping, preventing it taking up too much space, and makes it easy for people to copy your string for verification.
The leaderboard shows the last score present in the heading of your answer. This allows for including previous scores if you make improvements.
See also the example answer.
Verification
You can check your own string, or the string from another answer, using the cod golf validator.
Fishes
african glass catfish
african lungfish
aholehole
airbreathing catfish
airsac catfish
alaska blackfish
albacore
alewife
alfonsino
algae eater
alligator gar
alligatorfish
amberjack
american sole
amur pike
anchovy
anemonefish
angelfish
angler
angler catfish
anglerfish
antarctic cod
antarctic icefish
antenna codlet
arapaima
archerfish
arctic char
armored gurnard
armored searobin
armorhead
armorhead catfish
armoured catfish
arowana
arrowtooth eel
asian carp
asiatic glassfish
atka mackerel
atlantic bonito
atlantic cod
atlantic herring
atlantic pomfret
atlantic salmon
atlantic saury
atlantic sharpnose shark
atlantic silverside
atlantic spadefish
australasian salmon
australian grayling
australian herring
australian lungfish
australian prowfish
ayu
baikal oilfish
bala shark
ballan wrasse
bamboo shark
banded killifish
bandfish
bangus
banjo
banjo catfish
barb
barbel
barbel-less catfish
barbeled dragonfish
barbeled houndshark
barfish
barracuda
barracudina
barramundi
barred danio
barreleye
basking shark
bass
basslet
bat ray
batfish
beachsalmon
beaked salmon
beaked sandfish
beardfish
beluga sturgeon
bengal danio
betta
bichir
bicolor goat fish
bigeye
bigeye squaretail
bighead carp
bigmouth buffalo
bigscale
bigscale pomfret
billfish
bitterling
black angelfish
black bass
black dragonfish
black mackerel
black neon tetra
black scabbardfish
black scalyfin
black sea bass
black swallower
black tetra
black triggerfish
blackchin
blackfin tuna
blackfish
blacktip reef shark
bleak
blenny
blind goby
blind shark
blobfish
blowfish
blue catfish
blue danio
blue eye trevalla
blue gourami
blue shark
blue triggerfish
blue whiting
blue-redstripe danio
bluefin tuna
bluefish
bluegill
bluntnose knifefish
bluntnose minnow
boafish
boarfish
bobtail snipe eel
bocaccio
boga
bombay duck
bonefish
bonito
bonnethead shark
bonnetmouth
bonytail
bonytongue
bowfin
boxfish
bramble shark
bream
brill
bristlemouth
bristlenose catfish
broadband dogfish
bronze corydoras
brook lamprey
brook stickleback
brook trout
brotula
brown trout
buffalo fish
bull shark
bull trout
bullhead
bullhead shark
bumblebee goby
burbot
buri
burma danio
burrowing goby
butterfish
butterfly ray
butterflyfish
california flyingfish
california halibut
canary rockfish
candiru
candlefish
capelin
cardinal tetra
cardinalfish
carp
carpetshark
carpsucker
cat shark
catalufa
catfish
catla
cave angelfish
cavefish
celebes rainbowfish
central mudminnow
chain pickerel
channel bass
channel catfish
char
cherry salmon
cherubfish
chimaera
chinook salmon
chub
chubsucker
chum salmon
cichlid
cisco
climbing catfish
climbing gourami
climbing perch
clingfish
clown loach
clown triggerfish
clownfish
cobbler
cobia
cod
codlet
codling
coelacanth
coffinfish
coho salmon
coley
collared carpetshark
collared dogfish
colorado squawfish
combfish
combtail gourami
combtooth blenny
common carp
common tunny
conger eel
convict blenny
convict cichlid
cookie-cutter shark
coolie loach
cornetfish
cow shark
cowfish
cownose ray
crappie
creek chub
crestfish
crevice kelpfish
croaker
crocodile icefish
crocodile shark
crucian carp
cuckoo wrasse
cusk
cusk-eel
cutlassfish
cutthroat eel
cutthroat trout
dab
dace
daggertooth pike conger
damselfish
danio
darter
dartfish
dealfish
death valley pupfish
deep-sea eel
deep-sea smelt
deepwater cardinalfish
deepwater flathead
deepwater stingray
delta smelt
demoiselle
denticle herring
desert pupfish
devario
devil ray
dhufish
discus
dogfish
dogfish shark
dogteeth tetra
dojo loach
dolly varden trout
dolphin fish
dorab wolf-herring
dorado
dory
dottyback
dragon goby
dragonet
dragonfish
driftfish
driftwood catfish
drum
duckbill
duckbill eel
dusky grouper
dusky shark
dwarf gourami
dwarf loach
eagle ray
earthworm eel
eel
eel cod
eel-goby
eelpout
eeltail catfish
elasmobranch
electric catfish
electric eel
electric knifefish
electric ray
elephant fish
elephantnose fish
elver
ember parrotfish
emerald catfish
emperor
emperor angelfish
emperor bream
escolar
eucla cod
eulachon
european chub
european eel
european flounder
european minnow
european perch
false brotula
false cat shark
false moray
false trevally
fangtooth
fathead sculpin
featherback
fierasfer
filefish
finback cat shark
fingerfish
fire bar danio
fire goby
firefish
flabby whale fish
flagblenny
flagfin
flagfish
flagtail
flashlight fish
flatfish
flathead
flathead catfish
flier
flounder
flying fish
flying gurnard
footballfish
forehead brooder
four-eyed fish
french angelfish
freshwater eel
freshwater hatchetfish
freshwater shark
frigate mackerel
frilled shark
frogfish
frogmouth catfish
fusilier fish
galjoen fish
ganges shark
gar
garden eel
garibaldi
garpike
ghost fish
ghost flathead
ghost knifefish
ghost pipefish
ghost shark
ghoul
giant danio
giant gourami
giant sea bass
gibberfish
gila trout
gizzard shad
glass catfish
glass knifefish
glassfish
glowlight danio
goatfish
goblin shark
goby
golden dojo
golden loach
golden shiner
golden trout
goldeye
goldfish
gombessa
goosefish
gopher rockfish
gourami
grass carp
graveldiver
gray mullet
gray reef shark
grayling
great white shark
green spotted puffer
green swordtail
greeneye
greenling
grenadier
ground shark
grouper
grunion
grunt
grunt sculpin
grunter
gudgeon
guitarfish
gulf menhaden
gulper
gulper eel
gunnel
guppy
gurnard
haddock
hagfish
hairtail
hake
halfbeak
halfmoon
halibut
halosaur
hamlet
hammerhead shark
hammerjaw
handfish
hardhead catfish
harelip sucker
hatchetfish
hawkfish
herring
herring smelt
hickory shad
hillstream loach
hilsha
hog sucker
hoki
horn shark
horsefish
houndshark
huchen
humuhumunukunukuapua'a
hussar
icefish
ide
ilish
inanga
inconnu
jack
jack dempsey
jackfish
japanese eel
javelin
jawfish
jellynose fish
jewel tetra
jewelfish
john dory
kafue pike
kahawai
kaluga
kanyu
kelp perch
kelpfish
killifish
king of the herrings
king-of-the-salmon
kingfish
kissing gourami
knifefish
knifejaw
koi
kokanee
kokopu
kuhli loach
labyrinth fish
ladyfish
lake chub
lake trout
lake whitefish
lampfish
lamprey
lancetfish
lanternfish
largemouth bass
leaffish
leatherjacket
lefteye flounder
lemon shark
lemon sole
lemon tetra
lenok
leopard danio
lightfish
limia
lined sole
ling
ling cod
lionfish
livebearer
lizardfish
loach
loach catfish
loach goby
loach minnow
long-finned char
long-finned pike
long-finned sand diver
long-whiskered catfish
longfin
longfin dragonfish
longfin escolar
longfin smelt
longjaw mudsucker
longneck eel
longnose chimaera
longnose dace
longnose lancetfish
longnose sucker
longnose whiptail catfish
loosejaw
lost river sucker
louvar
loweye catfish
luderick
luminous hake
lumpsucker
lungfish
mackerel
mackerel shark
madtom
mahi-mahi
mahseer
mail-cheeked fish
mako shark
man-of-war fish
mandarinfish
manefish
manta ray
marblefish
marine hatchetfish
marlin
masu salmon
medaka
medusafish
megamouth shark
menhaden
merluccid hake
mexican golden trout
midshipman fish
milkfish
minnow
minnow of the deep
modoc sucker
mojarra
mola mola
monkeyface prickleback
monkfish
mooneye
moonfish
moorish idol
mora
moray eel
morid cod
morwong
moses sole
mosquitofish
mouthbrooder
mozambique tilapia
mrigal
mud catfish
mud minnow
mudfish
mudskipper
mudsucker
mullet
mummichog
murray cod
muskellunge
mustache triggerfish
mustard eel
naked-back knifefish
nase
needlefish
neon tetra
new world rivuline
new zealand sand diver
new zealand smelt
nibble fish
noodlefish
north american darter
north american freshwater catfish
north pacific daggertooth
northern anchovy
northern clingfish
northern lampfish
northern pike
northern sea robin
northern squawfish
northern stargazer
notothen
nurse shark
nurseryfish
oarfish
ocean perch
ocean sunfish
oceanic whitetip shark
oilfish
old world knifefish
oldwife
olive flounder
opah
opaleye
orange roughy
orangespine unicorn fish
orangestriped triggerfish
orbicular batfish
orbicular velvetfish
oregon chub
orfe
oriental loach
oscar
owens pupfish
pacific albacore
pacific cod
pacific hake
pacific herring
pacific lamprey
pacific rudderfish
pacific salmon
pacific saury
pacific trout
pacific viperfish
paddlefish
pancake batfish
panga
paradise fish
parasitic catfish
parore
parrotfish
peacock flounder
peamouth
pearl danio
pearl perch
pearleye
pearlfish
pelagic cod
pelican eel
pelican gulper
pencil catfish
pencilfish
pencilsmelt
peppered corydoras
perch
peters' elephantnose fish
pickerel
pigfish
pike
pike conger
pike eel
pikeblenny
pikeperch
pilchard
pilot fish
pineapplefish
pineconefish
pink salmon
pintano
pipefish
piranha
pirarucu
pirate perch
plaice
platy
platyfish
pleco
plownose chimaera
poacher
pollock
pollyfish
pomfret
pompano
pompano dolphinfish
ponyfish
popeye catalufa
porbeagle shark
porcupinefish
porgy
port jackson shark
powen
prickleback
pricklefish
prickly shark
prowfish
pufferfish
pumpkinseed
pupfish
pygmy sunfish
queen danio
queen parrotfish
queen triggerfish
quillback
quillfish
rabbitfish
raccoon butterfly fish
ragfish
rainbow trout
rainbowfish
rasbora
ratfish
rattail
ray
razorback sucker
razorfish
red grouper
red salmon
red snapper
red velvetfish
red whalefish
redfin perch
redfish
redhorse sucker
redlip blenny
redmouth whalefish
redtooth triggerfish
reedfish
reef triggerfish
remora
requiem shark
ribbon eel
ribbon sawtail fish
ribbonfish
rice eel
ricefish
ridgehead
riffle dace
righteye flounder
rio grande perch
river loach
river shark
river stingray
rivuline
roach
roanoke bass
rock bass
rock beauty
rock cod
rock gunnel
rocket danio
rockfish
rockling
rockweed gunnel
rohu
ronquil
roosterfish
ropefish
rough scad
rough sculpin
roughy
round herring
round stingray
round whitefish
roundhead
rudd
rudderfish
ruffe
russian sturgeon
sabalo
saber-toothed blenny
sabertooth
sabertooth fish
sablefish
sacramento blackfish
sacramento splittail
sailfin silverside
sailfish
salamanderfish
salmon
salmon shark
sand dab
sand diver
sand eel
sand goby
sand knifefish
sand lance
sand stargazer
sand tiger
sand tilefish
sandbar shark
sandburrower
sandfish
sandperch
sandroller
sarcastic fringehead
sardine
sargassum fish
sauger
saury
saw shark
sawfish
sawtooth eel
scabbard fish
scaly dragonfish
scat
scissortail rasbora
scorpionfish
sculpin
scup
sea bass
sea bream
sea catfish
sea chub
sea devil
sea dragon
sea lamprey
sea raven
sea snail
sea toad
seahorse
seamoth
searobin
sergeant major
sevan trout
shad
shark
sharksucker
sharpnose puffer
sheatfish
sheepshead
sheepshead minnow
shiner
shortnose chimaera
shortnose sucker
shovelnose sturgeon
shrimpfish
siamese fighting fish
sillago
silver carp
silver dollar
silver dory
silver hake
silverside
silvertip tetra
sind danio
sixgill ray
sixgill shark
skate
skilfish
skipjack tuna
sleeper
sleeper shark
slender mola
slender snipe eel
slickhead
slimehead
slimy mackerel
slimy sculpin
slipmouth
smalleye squaretail
smalltooth sawfish
smelt
smelt-whiting
smooth dogfish
snailfish
snake eel
snake mackerel
snakehead
snapper
snipe eel
snipefish
snook
snubnose eel
snubnose parasitic eel
sockeye salmon
soldierfish
sole
south american darter
south american lungfish
southern dolly varden
southern flounder
southern hake
southern sandfish
southern smelt
spadefish
spaghetti eel
spanish mackerel
spearfish
speckled trout
spiderfish
spikefish
spinefoot
spiny basslet
spiny dogfish
spiny dwarf catfish
spiny eel
spinyfin
splitfin
spookfish
spottail pinfish
spotted climbing perch
spotted danio
sprat
springfish
squarehead catfish
squaretail
squawfish
squeaker
squirrelfish
staghorn sculpin
stargazer
starry flounder
steelhead
stickleback
stingfish
stingray
stonecat
stonefish
stoneroller minnow
stream catfish
striped bass
striped burrfish
sturgeon
sucker
suckermouth armored catfish
summer flounder
sundaland noodlefish
sunfish
surf sardine
surfperch
surgeonfish
swallower
swamp-eel
swampfish
sweeper
swordfish
swordtail
tadpole cod
tadpole fish
tailor
taimen
tang
tapetail
tarpon
tarwhine
telescopefish
temperate bass
temperate ocean-bass
temperate perch
tench
tenpounder
tenuis
tetra
thornfish
thorny catfish
thread-tail
threadfin
threadfin bream
three spot gourami
three-toothed puffer
threespine stickleback
thresher shark
tidewater goby
tiger barb
tiger shark
tiger shovelnose catfish
tigerfish
tigerperch
tilapia
tilefish
titan triggerfish
toadfish
tommy ruff
tompot blenny
tonguefish
tope
topminnow
torpedo
torrent catfish
torrent fish
trahira
treefish
trevally
triggerfish
triplefin blenny
triplespine
tripletail
tripod fish
trout
trout cod
trout-perch
trumpeter
trumpetfish
trunkfish
tube-eye
tube-snout
tubeblenny
tubeshoulder
tui chub
tuna
turbot
two spotted goby
uaru
unicorn fish
upside-down catfish
vanjaram
velvet belly lanternshark
velvet catfish
velvetfish
vendace
vermilion snapper
vimba
viperfish
wahoo
walking catfish
wallago
walleye
walleye pollock
walu
warmouth
warty angler
waryfish
waspfish
weasel shark
weatherfish
weever
weeverfish
wels catfish
whale catfish
whale shark
whalefish
whiff
white croaker
white marlin
white shark
whitebait
whitefish
whitetip reef shark
whiting
wobbegong
wolf-eel
wolf-herring
wolffish
worm eel
wormfish
wrasse
wrymouth
x-ray tetra
yellow bass
yellow jack
yellow moray
yellow perch
yellow tang
yellow weaver
yellow-and-black triplefin
yellow-edged moray
yellow-eye mullet
yellowback fusilier
yellowbanded perch
yellowedge grouper
yellowfin croaker
yellowfin cutthroat trout
yellowfin grouper
yellowfin pike
yellowfin surgeonfish
yellowfin tuna
yellowhead jawfish
yellowmargin triggerfish
yellowtail
yellowtail amberjack
yellowtail barracuda
yellowtail catfish
yellowtail clownfish
yellowtail horse mackerel
yellowtail kingfish
yellowtail snapper
zander
zebra bullhead shark
zebra danio
zebra lionfish
zebra loach
zebra oto
zebra pleco
zebra shark
zebra tilapia
zebra turkeyfish
zebrafish
ziege
zingel
This list of fishes has been taken from "List of fish common names" on Wikipedia. This list contains 1091 fishes in total. As Wikipedia pages are prone to change over time, the list presented in this challenge is the only one that will be used for validating answers. Any typos or inaccuracies found in this list will not be corrected, to avoid invalidating any existing answers.
Explanations in answers are optional, but I'm more likely to upvote answers that have one.
+2
−0
C++, 64 bytes ``` gnopbris …
15d ago
+1
−0
Vyxal 3, 112 bytes ``` eµ⌈ …
15d ago
+0
−0
Python 3, 2963 bytes This i …
18d ago
3 answers
+2
−0
C++, 64 bytes
gnopbristh aloumericpaendogjaw fresmudolphwartingsucker caytfish
Found using another heuristic-based approach. In each iteration, we choose the string with the lowest ratio of length to number of contained fishes, and calculate the shortest common supersequence of it and every other string.
I left it running for a while and this was the best result, though it is possible if I ran it longer it might find something better.
Code
#include <algorithm>
#include <fstream>
#include <mdspan>
#include <print>
#include <ranges>
#include <set>
#include <string>
#include <string_view>
#include <vector>
void scs_table_fill(std::string_view a, std::string_view b,
std::vector<std::size_t> &buffer) {
auto const n = a.size();
auto const m = b.size();
buffer.reserve((n + 1) * (m + 1));
std::mdspan scs{buffer.data(), n + 1, m + 1};
for (std::size_t i = 0; i < n + 1; ++i) {
scs[i, 0] = i;
}
for (std::size_t j = 0; j < m + 1; ++j) {
scs[0, j] = j;
}
for (std::size_t i = 1; i < n + 1; ++i) {
for (std::size_t j = 1; j < m + 1; ++j) {
if (a[i - 1] == b[j - 1]) {
scs[i, j] = scs[i - 1, j - 1] + 1;
} else {
scs[i, j] = std::min(scs[i - 1, j], scs[i, j - 1]) + 1;
}
}
}
}
std::size_t scs_length(std::string_view a, std::string_view b,
std::size_t *buffer) {
auto const n = a.size();
auto const m = b.size();
std::mdspan scs{buffer, n + 1, m + 1};
return scs[n, m];
}
std::string scs_string(std::string_view a, std::string_view b,
std::size_t *buffer) {
auto const n = a.size();
auto const m = b.size();
std::mdspan scs{buffer, n + 1, m + 1};
std::string result;
result.reserve(scs[n, m]);
std::size_t i = n;
std::size_t j = m;
while (i > 0 and j > 0) {
if (a[i - 1] == b[j - 1]) {
result.push_back(a[i - 1]);
i--;
j--;
} else if (scs[i - 1, j] < scs[i, j - 1]) {
result.push_back(a[i - 1]);
i--;
} else {
result.push_back(b[j - 1]);
j--;
}
}
while (i > 0) {
result.push_back(a[i - 1]);
i--;
}
while (j > 0) {
result.push_back(b[j - 1]);
j--;
}
std::ranges::reverse(result);
return result;
}
struct scs_pair {
double ratio;
std::string string;
auto operator<=>(scs_pair const &other) const = default;
};
bool has_subsequence(std::string_view a, std::string_view b) {
char const *p = a.data();
char const *end = a.data() + a.size();
for (char c : b) {
while (p != end and *p != c) {
++p;
}
if (p == end) {
return false;
}
++p;
}
return true;
}
int main(int argc, char **argv) {
if (argc != 2) {
std::println(stderr, "Usage: {} <file>", argv[0]);
return 1;
}
std::vector<std::string> fishes;
std::ifstream ifs{argv[1]};
std::string line;
while (std::getline(ifs, line)) {
fishes.emplace_back(std::move(line));
}
std::println("Read {} fishes", fishes.size());
std::vector<std::size_t> buffer;
auto const count_fishes = [&](std::string_view string) {
return std::ranges::count_if(fishes, [&](auto const &fish) {
return has_subsequence(string, fish);
});
};
std::set<std::string> strings{std::from_range, fishes};
std::set<scs_pair> pairs;
for (auto a = strings.begin(); a != strings.end(); ++a) {
for (auto b = strings.begin(); b != a; ++b) {
auto &a_str = *a;
auto &b_str = *b;
scs_table_fill(a_str, b_str, buffer);
auto scs = scs_string(a_str, b_str, buffer.data());
if (strings.contains(scs)) {
continue;
}
auto count = count_fishes(scs);
double ratio = static_cast<double>(scs.size()) / count;
pairs.emplace(ratio, scs);
}
}
std::string current_solution;
while (true) {
auto iter = pairs.begin();
auto count = count_fishes(iter->string);
if (count >= 255) {
if (iter->string.size() < current_solution.size() ||
current_solution.empty()) {
std::println("Possible solution: {} ({}, {}, {})", iter->string, iter->string.size(), count, iter->ratio);
current_solution = iter->string;
}
} else {
for (auto &a_str : strings) {
scs_table_fill(a_str, iter->string, buffer);
auto scs = scs_string(a_str, iter->string, buffer.data());
if (strings.contains(scs)) {
continue;
}
auto count = count_fishes(scs);
double ratio = static_cast<double>(scs.size()) / count;
pairs.emplace(ratio, scs);
}
strings.emplace(iter->string);
}
pairs.erase(iter);
}
}
C++, 72 bytes
spncfljorath bamverbolppiufngczaone frdeshdlowatbveryc icdatknbfisthlaeo
Done using a simple heuristic-based approach. We maintain a set of strings, and in each iteration attempt to find the pair of strings that has the smallest increase in length when merged into their shortest common supersequence.
We repeat until we find a string with at least 255 fishes.
Code
#include <algorithm>
#include <fstream>
#include <map>
#include <mdspan>
#include <memory>
#include <print>
#include <set>
#include <string>
#include <string_view>
#include <vector>
void scs_table_fill(std::string_view a, std::string_view b, auto scs) {
auto const n = a.size();
auto const m = b.size();
for (std::size_t i = 0; i < n + 1; ++i) {
scs[i, 0] = i;
}
for (std::size_t j = 0; j < m + 1; ++j) {
scs[0, j] = j;
}
for (std::size_t i = 1; i < n + 1; ++i) {
for (std::size_t j = 1; j < m + 1; ++j) {
if (a[i - 1] == b[j - 1]) {
scs[i, j] = scs[i - 1, j - 1] + 1;
} else {
scs[i, j] = std::min(scs[i - 1, j], scs[i, j - 1]) + 1;
}
}
}
}
std::size_t scs_length(std::string_view a, std::string_view b) {
auto const n = a.size();
auto const m = b.size();
auto dp = std::make_unique<std::size_t[]>((n + 1) * (m + 1));
std::mdspan scs{dp.get(), n + 1, m + 1};
scs_table_fill(a, b, scs);
return scs[n, m];
}
std::string scs_string(std::string_view a, std::string_view b) {
auto const n = a.size();
auto const m = b.size();
auto dp = std::make_unique<std::size_t[]>((n + 1) * (m + 1));
std::mdspan scs{dp.get(), n + 1, m + 1};
scs_table_fill(a, b, scs);
std::string result;
std::size_t i = n;
std::size_t j = m;
while (i > 0 and j > 0) {
if (a[i - 1] == b[j - 1]) {
result.push_back(a[i - 1]);
i--;
j--;
} else if (scs[i - 1, j] < scs[i, j - 1]) {
result.push_back(a[i - 1]);
i--;
} else {
result.push_back(b[j - 1]);
j--;
}
}
while (i > 0) {
result.push_back(a[i - 1]);
i--;
}
while (j > 0) {
result.push_back(b[j - 1]);
j--;
}
std::ranges::reverse(result);
return result;
}
int main(int argc, char **argv) {
if (argc != 2) {
std::println(stderr, "Usage: {} <file>", argv[0]);
return 1;
}
std::vector<std::string> fishes;
std::ifstream ifs{argv[1]};
std::string buffer;
while (std::getline(ifs, buffer)) {
fishes.emplace_back(std::move(buffer));
}
std::println("Read {} fishes", fishes.size());
std::map<std::string, std::set<std::string_view>> strings;
auto const count_fishes = [&](std::string_view string,
std::set<std::string_view> &contains) {
for (std::string const &fish : fishes) {
if (string.size() >= fish.size() and
scs_length(string, fish) == string.size()) {
contains.emplace(fish);
}
}
};
for (std::string const &fish : fishes) {
std::set<std::string_view> contains;
count_fishes(fish, contains);
strings.emplace(fish, std::move(contains));
}
while (true) {
decltype(strings)::iterator best_a, best_b;
std::size_t best_delta = std::numeric_limits<std::size_t>::max();
auto const reset_best = [&] {
best_delta = std::numeric_limits<std::size_t>::max();
best_a = {};
best_b = {};
};
auto a = strings.begin();
outer:
while (a != strings.end()) {
auto b = strings.begin();
while (b != a) {
auto &[a_str, a_set] = *a;
auto &[b_str, b_set] = *b;
auto scs_len = scs_length(a_str, b_str);
// is this a good heuristic? who knows
auto delta = scs_len - std::max(a_str.size(), b_str.size());
if (delta == 0) {
if (a_str.size() > b_str.size()) {
if (best_a == b or best_b == b) {
reset_best();
}
std::println("'{}' -> '{}'", b_str, a_str);
b = strings.erase(b);
} else {
if (best_a == a or best_b == a) {
reset_best();
}
std::println("'{}' -> '{}'", a_str, b_str);
a = strings.erase(a);
goto outer;
}
} else if (delta < best_delta) {
best_a = a;
best_b = b;
best_delta = delta;
++b;
} else {
++b;
}
}
++a;
}
if (best_delta == std::numeric_limits<std::size_t>::max()) {
continue;
}
auto &[a_str, a_set] = *best_a;
auto &[b_str, b_set] = *best_b;
auto scs = scs_string(a_str, b_str);
std::set<std::string_view> merged;
count_fishes(scs, merged);
if (merged.size() >= 255) {
std::println("{}", scs);
for (auto const &fish : merged) {
std::print("'{}' ", fish);
}
break;
}
std::println("'{}' '{}' -> '{}' ({})", a_str, b_str, scs, merged.size());
strings.erase(best_a);
strings.erase(best_b);
strings.emplace(std::move(scs), std::move(merged));
}
}
1 comment thread
+1
−0
Vyxal 3, 112 bytes
eµ⌈L|⌈hLN}⇄ƛ⌈h}u "fish"-21⊖“" dcatfnisharkeelmond"+
newkingnorthminnowtworiooldportlostgrayfirebluezebratigerthreespinysouthgreengreatgiantfalse dcatfnisharkeelmond
eµ⌈L|⌈hLN}⇄ƛ⌈h}u "fish"-21⊖“" dcatfnisharkeelmond"+
e # split the list on newlines
µ | } # sort by:
⌈L # split on spaces: length of resulting array
⌈hLN # secondary key: length of the first word, negative (we want fishes with many words but few letters)
⇄ # reverse to put the biggest sorts at the beginning
ƛ⌈h} # keep only the first word
u # uniquify
"fish"- # remove any instance of "fish", since we're going to include it later.
21⊖“ # take the first 21 fishes (found by binary search), join them on empty string
" dcatfnisharkeelmond"+ # append literal string, that counts for
# danio, catfish, shark, eel, salmond and possibly one or two other common suffixes.
💎
Created with the help of Luminespire.
267 fishes are included.
+0
−0
Python 3, 2963 bytes
This is a simple example answer.
The following code takes the newline separated list of all fishes as input and returns the concatenated first 255 of them.
def fish_string(all_fishes):
fish_list = all_fishes.split("\n")
return "".join(fish_list[:255])
if __name__ == "__main__":
import sys
all_fishes = sys.argv[1]
print(fish_string(all_fishes))
This gives the string:
african glass catfishafrican lungfishaholeholeairbreathing catfishairsac catfishalaska blackfishalbacorealewifealfonsinoalgae eateralligator garalligatorfishamberjackamerican soleamur pikeanchovyanemonefishangelfishanglerangler catfishanglerfishantarctic codantarctic icefishantenna codletarapaimaarcherfisharctic chararmored gurnardarmored searobinarmorheadarmorhead catfisharmoured catfisharowanaarrowtooth eelasian carpasiatic glassfishatka mackerelatlantic bonitoatlantic codatlantic herringatlantic pomfretatlantic salmonatlantic sauryatlantic sharpnose sharkatlantic silversideatlantic spadefishaustralasian salmonaustralian graylingaustralian herringaustralian lungfishaustralian prowfishayubaikal oilfishbala sharkballan wrassebamboo sharkbanded killifishbandfishbangusbanjobanjo catfishbarbbarbelbarbel-less catfishbarbeled dragonfishbarbeled houndsharkbarfishbarracudabarracudinabarramundibarred daniobarreleyebasking sharkbassbassletbat raybatfishbeachsalmonbeaked salmonbeaked sandfishbeardfishbeluga sturgeonbengal daniobettabichirbicolor goat fishbigeyebigeye squaretailbighead carpbigmouth buffalobigscalebigscale pomfretbillfishbitterlingblack angelfishblack bassblack dragonfishblack mackerelblack neon tetrablack scabbardfishblack scalyfinblack sea bassblack swallowerblack tetrablack triggerfishblackchinblackfin tunablackfishblacktip reef sharkbleakblennyblind gobyblind sharkblobfishblowfishblue catfishblue danioblue eye trevallablue gouramiblue sharkblue triggerfishblue whitingblue-redstripe daniobluefin tunabluefishbluegillbluntnose knifefishbluntnose minnowboafishboarfishbobtail snipe eelbocacciobogabombay duckbonefishbonitobonnethead sharkbonnetmouthbonytailbonytonguebowfinboxfishbramble sharkbreambrillbristlemouthbristlenose catfishbroadband dogfishbronze corydorasbrook lampreybrook sticklebackbrook troutbrotulabrown troutbuffalo fishbull sharkbull troutbullheadbullhead sharkbumblebee gobyburbotburiburma danioburrowing gobybutterfishbutterfly raybutterflyfishcalifornia flyingfishcalifornia halibutcanary rockfishcandirucandlefishcapelincardinal tetracardinalfishcarpcarpetsharkcarpsuckercat sharkcatalufacatfishcatlacave angelfishcavefishcelebes rainbowfishcentral mudminnowchain pickerelchannel basschannel catfishcharcherry salmoncherubfishchimaerachinook salmonchubchubsuckerchum salmoncichlidciscoclimbing catfishclimbing gouramiclimbing perchclingfishclown loachclown triggerfishclownfishcobblercobiacodcodletcodlingcoelacanthcoffinfishcoho salmoncoleycollared carpetsharkcollared dogfishcolorado squawfishcombfishcombtail gouramicombtooth blennycommon carpcommon tunnyconger eelconvict blennyconvict cichlidcookie-cutter sharkcoolie loachcornetfishcow sharkcowfishcownose raycrappiecreek chubcrestfishcrevice kelpfishcroakercrocodile icefishcrocodile sharkcrucian carpcuckoo wrassecuskcusk-eelcutlassfishcutthroat eelcutthroat troutdabdacedaggertooth pike congerdamselfishdaniodarterdartfishdealfishdeath valley pupfish
The online validator shows the score of 2963 (the length of the string) and that there are 1087 fishes included (even though only 255 were explicitly concatenated). In fact, only 4 of the total 1091 fishes are excluded. All of the others are accidentally included, because letters from the first 255 happen to be in the correct order to spell out others. This gives an idea of how much this could be improved.
To generate this string, you can save the code as cod-golf-answer.py and then enter the following in the terminal, pasting in the newline separated list of all fishes from the challenge wording between the double quotes:
python cod-golf-answer.py ""
0 comment threads
0 comment threads