29
\$\begingroup\$

There are a lot™ of pokemon. One of the defining characteristics of pokemon is their type, of which every1 pokemon has up to two types, a primary type and an optional secondary type. There are mechanical implications to each type, and so it is very useful to know what type a given pokemon is during battle. But there's no way that I'm going to memorize the type(s) of every single possible pokemon. So I need you to write me a program that takes the name of a pokemon as input, and outputs what type(s) this pokemon (probably) is.

Probably, you say? This is because it would be difficult to correctly identify every single pokemon's type(s), especially if you're trying to make your program as short as possible. So you do not need to identify every single pokemon with 100% reliability, you just need to make a reasonably good guess. You must find the optimal balance between identifying as many pokemon as possible, and keeping your code as short as possible. Your entry's score is calculated as follows:

Length of program * (1 / ratio of correct guesses) ^ 2

For example, if you wrote a program that was 500 bytes long, and it correctly identifies 50% of inputs, your score would be 2000 (500 * (1/0.5)^2) == 500 * 4, and a program that is 1000 bytes long that correctly identifies all of the inputs would have a score of 1000. For the purposes of scoring, 1/0 will be considered to equal infinity (so you better identify at least one of them correctly).

Since there are a lot™ of pokemon, we'll restrict this challenge to the first generation of pokemon, of which there are 151 pokemon2 and 17 types3. Here is a dataset of all the gen 1 pokemon by name, pokedex number, and type(s).

#,Name,Type 1,Type 2
1,Bulbasaur,Grass,Poison
2,Ivysaur,Grass,Poison
3,Venusaur,Grass,Poison
4,Charmander,Fire,
5,Charmeleon,Fire,
6,Charizard,Fire,Flying
7,Squirtle,Water,
8,Wartortle,Water,
9,Blastoise,Water,
10,Caterpie,Bug,
11,Metapod,Bug,
12,Butterfree,Bug,Flying
13,Weedle,Bug,Poison
14,Kakuna,Bug,Poison
15,Beedrill,Bug,Poison
16,Pidgey,Normal,Flying
17,Pidgeotto,Normal,Flying
18,Pidgeot,Normal,Flying
19,Rattata,Normal,
20,Raticate,Normal,
21,Spearow,Normal,Flying
22,Fearow,Normal,Flying
23,Ekans,Poison,
24,Arbok,Poison,
25,Pikachu,Electric,
26,Raichu,Electric,
27,Sandshrew,Ground,
28,Sandslash,Ground,
29,Nidoran,Poison,
30,Nidorina,Poison,
31,Nidoqueen,Poison,Ground
32,Nidoran,Poison,
33,Nidorino,Poison,
34,Nidoking,Poison,Ground
35,Clefairy,Fairy,
36,Clefable,Fairy,
37,Vulpix,Fire,
38,Ninetales,Fire,
39,Jigglypuff,Normal,Fairy
40,Wigglytuff,Normal,Fairy
41,Zubat,Poison,Flying
42,Golbat,Poison,Flying
43,Oddish,Grass,Poison
44,Gloom,Grass,Poison
45,Vileplume,Grass,Poison
46,Paras,Bug,Grass
47,Parasect,Bug,Grass
48,Venonat,Bug,Poison
49,Venomoth,Bug,Poison
50,Diglett,Ground,
51,Dugtrio,Ground,
52,Meowth,Normal,
53,Persian,Normal,
54,Psyduck,Water,
55,Golduck,Water,
56,Mankey,Fighting,
57,Primeape,Fighting,
58,Growlithe,Fire,
59,Arcanine,Fire,
60,Poliwag,Water,
61,Poliwhirl,Water,
62,Poliwrath,Water,Fighting
63,Abra,Psychic,
64,Kadabra,Psychic,
65,Alakazam,Psychic,
66,Machop,Fighting,
67,Machoke,Fighting,
68,Machamp,Fighting,
69,Bellsprout,Grass,Poison
70,Weepinbell,Grass,Poison
71,Victreebel,Grass,Poison
72,Tentacool,Water,Poison
73,Tentacruel,Water,Poison
74,Geodude,Rock,Ground
75,Graveler,Rock,Ground
76,Golem,Rock,Ground
77,Ponyta,Fire,
78,Rapidash,Fire,
79,Slowpoke,Water,Psychic
80,Slowbro,Water,Psychic
81,Magnemite,Electric,Steel
82,Magneton,Electric,Steel
83,Farfetch'd,Normal,Flying
84,Doduo,Normal,Flying
85,Dodrio,Normal,Flying
86,Seel,Water,
87,Dewgong,Water,Ice
88,Grimer,Poison,
89,Muk,Poison,
90,Shellder,Water,
91,Cloyster,Water,Ice
92,Gastly,Ghost,Poison
93,Haunter,Ghost,Poison
94,Gengar,Ghost,Poison
95,Onix,Rock,Ground
96,Drowzee,Psychic,
97,Hypno,Psychic,
98,Krabby,Water,
99,Kingler,Water,
100,Voltorb,Electric,
101,Electrode,Electric,
102,Exeggcute,Grass,Psychic
103,Exeggutor,Grass,Psychic
104,Cubone,Ground,
105,Marowak,Ground,
106,Hitmonlee,Fighting,
107,Hitmonchan,Fighting,
108,Lickitung,Normal,
109,Koffing,Poison,
110,Weezing,Poison,
111,Rhyhorn,Ground,Rock
112,Rhydon,Ground,Rock
113,Chansey,Normal,
114,Tangela,Grass,
115,Kangaskhan,Normal,
116,Horsea,Water,
117,Seadra,Water,
118,Goldeen,Water,
119,Seaking,Water,
120,Staryu,Water,
121,Starmie,Water,Psychic
122,Mr. Mime,Psychic,Fairy
123,Scyther,Bug,Flying
124,Jynx,Ice,Psychic
125,Electabuzz,Electric,
126,Magmar,Fire,
127,Pinsir,Bug,
128,Tauros,Normal,
129,Magikarp,Water,
130,Gyarados,Water,Flying
131,Lapras,Water,Ice
132,Ditto,Normal,
133,Eevee,Normal,
134,Vaporeon,Water,
135,Jolteon,Electric,
136,Flareon,Fire,
137,Porygon,Normal,
138,Omanyte,Rock,Water
139,Omastar,Rock,Water
140,Kabuto,Rock,Water
141,Kabutops,Rock,Water
142,Aerodactyl,Rock,Flying
143,Snorlax,Normal,
144,Articuno,Ice,Flying
145,Zapdos,Electric,Flying
146,Moltres,Fire,Flying
147,Dratini,Dragon,
148,Dragonair,Dragon,
149,Dragonite,Dragon,Flying
150,Mewtwo,Psychic,
151,Mew,Psychic,

And here is a list of all the available types:

Bug
Dragon
Electric
Fairy
Fighting
Fire
Flying
Ghost
Grass
Ground
Ice
Normal
Poison
Psychic
Rock
Steel
Water

Your input will always be one of the specified 151 gen 1 pokemon2. Your output must be one or two of the specified types. If outputting multiple types, you can choose the format to return them in (for example, separated by a space or a comma), but it must be consistent. Your input and output may be of any combination of upper and lower case that you require, just please specify what casing is required for your submission.

To count as a correct guess, you must match both types exactly. For example, outputting just "fire" for charizard, or outputting "ground + <anything else>" for diglett, both of these would be considered an entirely wrong guess.

Notes/edge cases

  • Entry 29 in the Pokedex is "Nidoran (female)", and entry 32 is "Nidoran (male)". Because both of these are just "Poison" type, the input will simply be "Nidoran", with no male/female designation. For calculating "ratio of correct guesses", treat Nidoran as a single entry (number of correct guesses / 150).
  • Every entry is comprised of only alphabetical characters with the following exceptions. To score these as correct guesses, the punctuation and spaces may not be removed or altered.
    • 83: Farfetch'd (Normal, Flying)
    • 122: Mr. Mime (Psychic, Fairy)
  • In pokemon mechanics, the order of the types is significant, as in "Type A/Type B" is different than "Type B/Type A". This is ignored for the purposes of this challenge, e.g. "Bulbasaur is 'Grass,Poison', but an output of 'Poison,Grass' is considered correct." The only types that Gen 1 pokemon have in both orders are "Rock/Ground" and "Ground/Rock" types, which are listed separately in the dataset, but can be counted as the same type for this challenge.

  • 1: There is arguably also a "???" type, which may or may not count as being a type.
  • 2: See Nidoran.
  • 3: Pokebiology was very primitive in the year of 1996, and both Fairy and Steel types were not yet recognized as being their own type when Gen 1 was released. Nevertheless, this challenge uses types as understood by our current modern day understanding of pokebiology.
\$\endgroup\$
9
  • \$\begingroup\$ I'm a little bit unsure whether this counts as kolmogorov-complexity and decision-problem. Thoughts? \$\endgroup\$
    – DJMcMayhem
    Sep 9, 2023 at 17:56
  • \$\begingroup\$ Are we allowed to make HTTP requests? It would kind of trivialize the challenge but you don't say anything about it. \$\endgroup\$
    – chunes
    Sep 9, 2023 at 18:30
  • 6
    \$\begingroup\$ @chunes isn't that a standard loophole? \$\endgroup\$
    – MTN
    Sep 9, 2023 at 18:33
  • 1
    \$\begingroup\$ you forgot the dark type which also does not appear in gen 1 \$\endgroup\$
    – pacman256
    Sep 9, 2023 at 19:34
  • 1
    \$\begingroup\$ @Pacmanboss256 Yes, that's why I didn't list it. \$\endgroup\$
    – DJMcMayhem
    Sep 9, 2023 at 19:40

10 Answers 10

26
\$\begingroup\$

Jelly, 181 bytes, accuracy 148/150, score ≈ 185.925

ȷ;€ȷḥ€⁸ḣ5¤ḋ“¢ṣẉṙ.þbɦṪỊ2ßẓʂẹ{©ṗḷ⁺¶ɱıEDẓẇlR³ṣɼcṭɲ9^O⁹¿ƭ{ÑṬṄLȥȧ§Spṗ¡¶?ṁcØÑ"Ḷ9ọẈ⁽~ƊŒ°Fȷðḳẓ@*Ƙ>Uƭ⁺aɦṪṇẈfẸȥsɱƑhṁt/.rẏỊSṠ8Ġe¥Ṡ )§’b97¤%97ḃ⁴UÄị“Ḅ ṚṘṢOṚıƁqø⁷)^ʋ<:Ɓ(ʠKħ)ṬƘH1ḍ×Uµ(5;§XMoƑ»ḲŒt¤

Try it online!

Function submission: outputs a list of 1 or 2 type names. The footer in the TIO! link runs the program on all possible inputs.

Explanation

Algorithm

This is mostly based on my standard "map these large inputs to these small outputs" program, which I've used on many questions before (see this answer and this answer for the history), and it's reached the point that these questions can mostly be answered in an automated way: here's the program that generated the bulk of this answer. The basic idea is to write a program that runs the input through a lot of different hash functions, then take the dot product of the hashes with a hardcoded vector in a finite field – working out an appropriate hardcoded vector for this is simply a case of solving a lot of simultaneous linear equations, which is trivial for a computer to do.

This time, though, there was a bit more manual work and ingenuity involved than usual. One observation is that a lossy algorithm is permitted (at a cost in score), so I chose to look at only the first five characters of each Pokémon's name (or all of them, if the name is shorter than that); this introduces a large number of beneficial collisions (turns out that Pokémon whose name start the same way normally have the same type!), and there are only two collisions that lead to incorrect results: Dragonite with Dragonair, ("Drago"), and Poliwrath with Poliwag and Poliwhirl ("Poliw" – Poliwag and Poliwhirl have the same type, but Poliwrath's is different). This produces a lot of savings, both due to the beneficial collisions, and because Dragonite and Poliwrath have unique types that would otherwise be difficult to encode.

The next trick was to order the types carefully. Each type is internally stored as a number, in the order fighting ghost fairy Grass dragon normal poison psychic bug water flying ground Ice fire rock electric steel (which is what the compressed string “Ḅ ṚṘṢOṚıƁqø⁷)^ʋ<:Ɓ(ʠKħ)ṬƘH1ḍ×Uµ(5;§XMoƑ» near the end of the program decompresses to – most types are shorter in lowercase, but Grass and Ice are shorter in titlecase for some reason). This order was chosen with a lot of manual experimentation so that for all dual-typed Pokémon, their types are at most five elements apart in the list. A type or type pair can then be encoded as a one- or two-digit number in bijective base 16, with the less significant digit being the lower-numbered type, and the more significant digit being the distance between the types; this encoding maps all the type pairings onto the range 1 (pure Fighting) to 91 (Electric/Flying). This reduces the codomain of the mapping function, and thus means that the hardcoded vector can contain smaller numbers and thus be shorter. An advantage of skipping Dragonite and Poliwrath is that their types would not encode very well in this pattern, with Dragon being six spaces from Flying in the list, and Fighting nine spaces away from Water.

Possible improvement: using a smaller modulus than 97, which is a little wasteful. I realised while writing this proof that it's actually OK for the modulus to not be prime – you can use two or more different finite fields and combine the results into a single vector that works modulo a non-prime. (In theory this would work for any size of codomain, although Jelly doesn't have finite field operators so it would only be easily expressible in Jelly for square-free numbers.) The odds of the equations being unsolvable would be higher, but hopefully it wouldn't be too bad to calculate them. I'd need to generate a new encoding program to be able to handle that, though.

Expressing the algorithm in Jelly

ȷ;€ȷḥ€⁸ḣ5¤ḋ“…’b97¤%97ḃ⁴UÄị“…»ḲŒt¤
ȷ;€ȷ                               1000 hash function configurations
    ḥ€                             with each of them, hash
       ḣ5                            the first 5 characters of
      ⁸  ¤                           the function input
          ḋ      ¤                 dot product with
           “…’                       a very large hardcoded number
              b97                    converted to base 97 digits
                  %97              take the result modulo 97
                     ḃ⁴            express in bijective base 16
                       U           reverse digit order
                        Ä          cumulative sum
                         ị      ¤  index into
                          “…»        a hardcoded compressed string
                             Ḳ       split on spaces
                              Œt     and converted to titlecase

The first large constant is the vector used to do the mapping. The second is the list of type names – it was shorter to write this in mixed case and fix the case later than it would have been to write it in the correct case from the start.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Why is this CW? \$\endgroup\$ Sep 10, 2023 at 4:13
  • \$\begingroup\$ Did you try only matching the more common types? It's possible that the cost of encoding the rarer types is more than the benefit they give \$\endgroup\$ Sep 10, 2023 at 4:26
  • 2
    \$\begingroup\$ @CommandMaster: I did. The best attempt is to omit Steel, but it ends up costing more in accuracy penalties than it saves in bytes. (Also, I CW all my answers in an attempt to avoid reputation – the reputation game on Stack Exchange is broken and pushes people into writing bad answers. I used to be able to repcap on pretty much any day I wanted to, but generally at the cost of needing to write popular answers/questions rather than ones that are interesting or worthwhile, so I deleted my >20k account and have now recreated one that's intentionally permanently stuck at 11 reputation.) \$\endgroup\$
    – ais523
    Sep 10, 2023 at 4:40
  • \$\begingroup\$ Grass is title cased in Jelly's dictionary for some reason. Ice isn't a dictionary word so I don't know how that relates to Jelly's string compression. \$\endgroup\$
    – Neil
    Sep 10, 2023 at 11:49
22
\$\begingroup\$

PHP, 5 bytes, score = 347.222

Correctly guesses 18 Pokemon.

Water

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Nitpick, but I believe your score is 347.222. There are 150 distinct inputs, not 151 (See Nidoran) \$\endgroup\$
    – DJMcMayhem
    Sep 9, 2023 at 19:13
  • \$\begingroup\$ @DJMcMayhem Thanks, I kind of skimmed through the rules on scoring there. Anyway, it helps my score :) \$\endgroup\$ Sep 9, 2023 at 19:27
  • \$\begingroup\$ Me trying to find the most common type but finding that you already found that it is water: \$\endgroup\$
    – Joao-3
    Sep 10, 2023 at 20:48
  • 1
    \$\begingroup\$ Lol I was about to attempt the same solution, simple yet pretty effective :) \$\endgroup\$
    – Patronics
    Sep 11, 2023 at 4:13
13
\$\begingroup\$

Node.js, score = 579 (579 bytes, 100%)

This is at the other end of the spectrum, as opposed to @dingledooper's answer, as it gives the correct answer for all inputs.

s=>(g=i=>["GrassPoisonFireFlyingWaterBugNormalElectricGroundFairyFightingPsychicRockSteelIceGhostDragon".match(/.[a-z]+/g)[(B=Buffer)(`7$1 !7$<)&5!4$J%8,$*6#$?!P*<!4'R.+#&9$B !=,$M(!9%!"B+$K$B04$d%!3% 5%!A(@.$;+J*:#&3#&=&N$@*$&1(: P$6 !?(,9&6#!K/!"#3(T$6(,S&N$B$J#!? !?(,7!6"1!1'J!>*H"@*T,$5 !C(6%!.$3%@'-+$C+>&<(,9!8+J+P"1 +% O+>*4#&#&#&_!J0J!6'p(<#.=#&S"4&:$8+8):)F +7'< !="6)&o/!$J)+7'#g+$a$1!$.$;#&3&X&1#,="l$1"1'Z'-&1"Z(,= !A"V0#Q&4&4(!= !W%4$4%!;%#c+L$x%#7,$5*8!$K/!y"#G !3'6(:(,&`.replace(/[2-~]/g,c=>"1".repeat(B(c)[0]-49)))[parseInt(s,36)%9313%1248*2|i]-32]])``+" "+g(1)

Try it online!

\$\endgroup\$
3
  • 5
    \$\begingroup\$ It's a bummer that this scores so much higher than the other answer. Perhaps I should have tweaked the scoring a little bit. \$\endgroup\$
    – DJMcMayhem
    Sep 9, 2023 at 22:19
  • 1
    \$\begingroup\$ @DJMcMayhem Yes, dingledooper's answer is likely to give the best possible score for non-golfing languages. And maybe the best possible score for golfing languages is obtained with the shortest compressed form of "water". \$\endgroup\$
    – Arnauld
    Sep 9, 2023 at 22:24
  • 1
    \$\begingroup\$ @DJMcMayhem Well, I managed to get my score down to 8/7 of what the "port" (it's a polyglot) of @dingledooper's answer would score. \$\endgroup\$
    – Neil
    Sep 9, 2023 at 23:22
12
\$\begingroup\$

jAvAscRIpt, 273 characters, score = 322.5425

This answer includes insincere rules-lawyering, but it doesn't seem to literally abuse a standard loophole. It might count as "adding input or rules".

Since the Question says

"If outputting multiple types, you can choose the format to return them in (for example, separated by a space or a comma), but it must be consistent. Your input and output may be of any combination of upper and lower case that you require, just please specify what casing is required for your submission."

,

inputs to this submission must follow the casing of the revised Pokéorthography (that I made up) to have it generate the correct answer 138 out of 150 times. This is the revised Pokéorthography:

muk Poison 
Mew Psychic 
Abra Psychic 
seEl Water 
ONIx Rock Ground
JynX Psychic Ice
ekans Poison 
arbok Poison 
zUbAt Poison Flying
glooM Grass Poison
ParaS Bug Grass
GOLem Rock Ground
dODUO Normal Flying
Hypno Psychic 
diTtO Normal 
eeVeE Normal 
WeedLE Bug Poison
KakuNA Bug Poison
pIDGEy Normal Flying
fEAROw Normal Flying
RaIcHu Electric 
vulpix Fire 
gOlBat Poison Flying
oddiSH Grass Poison
meOwTh Normal 
mankey Fighting 
machop Fighting 
ponyta Fire 
dODRIo Normal Flying
grimer Poison 
gastlY Ghost Poison
gengaR Ghost Poison
krAbby Water 
cubone Ground 
RHYdon Rock Ground
hoRsea Water 
seAdra Water 
stAryu Water 
magmar Fire 
PinsIr Bug 
taUrOs Normal 
lapRaS Ice Water
KaBUtO Rock Water
ZAPDOs Electric Flying
Mewtwo Psychic 
ivysAUr Grass Poison
MetaPod Bug 
pIDGEot Normal Flying
raTtAta Normal 
sPEARow Normal Flying
PiKaChu Electric 
nidoran Poison 
nidoran Poison 
VenoNAt Bug Poison
DiGletT Ground 
DuGtriO Ground 
peRsIan Normal 
psYduck Water 
goLduck Water 
poLiwag Water 
Kadabra Psychic 
MachokE Fighting 
MachamP Fighting 
GEOdude Rock Ground
SloWbRo Psychic Water
dewGONG Ice Water
haUntER Ghost Poison
Drowzee Psychic 
kiNgler Water 
VoLtOrb Electric 
MaRowaK Ground 
koffing Poison 
weezing Poison 
RHYhorn Rock Ground
chAnSey Normal 
tangEla Grass 
goLdeen Water 
seAking Water 
StaRmIe Psychic Water
SCyTHer Bug Flying
JoLtEon Electric 
flareoN Fire 
poRyGon Normal 
OmANyTe Rock Water
OmAStAr Rock Water
snOrLax Normal 
mOlTreS Fire Flying
DratInI Dragon 
venuSAur Grass Poison
sqUirtle Water 
CateRpie Bug 
BeedRIll Bug Poison
raTiCate Normal 
nidorina Poison 
nidorino Poison 
nIdoking Poison Ground
clEfAiRy Fairy 
clEfAbLe Fairy 
PAraSEct Bug Grass
VenoMOth Bug Poison
PrimeaPe Fighting 
arcaniNe Fire 
Alakazam Psychic 
GRAveler Rock Ground
rapidaSh Fire 
SloWpOke Psychic Water
MAGNETon Electric Steel
shEllder Water 
cloYSTEr Ice Water
Mr. mimE Psychic Fairy
maGikarp Water 
gYARados Water Flying
vaPoreon Water 
KaBUtOps Rock Water
aRtICuNo Ice Flying
bulbASaur Grass Poison
cHaRizArd Fire Flying
waRtortle Water 
blAstoise Water 
pIDGEotto Normal Flying
SaNdshRew Ground 
SaNdslAsh Ground 
nIdoqueen Poison Ground
ninetaLes Fire 
vilePLume Grass Poison
growliThe Fire 
poLiwhirl Water 
PolIwRAth Fighting Water
teNtaCool Water Poison
MAGNEMite Electric Steel
ElEcTrode Electric 
EXeggCute Psychic Grass
EXeggUtor Psychic Grass
HitmonLee Fighting 
liCkItung Normal 
DragOnAir Dragon 
DRaGOnIte Dragon Flying
charmaNder Fire 
charmeLeon Fire 
BUtTErfree Bug Flying
jiGgLypUff Normal Fairy
wiGgLytUff Normal Fairy
bellSProut Grass Poison
weepINbell Grass Poison
victREebel Grass Poison
teNtaCruel Water Poison
fARFEtch'd Normal Flying
HitmonChan Fighting 
kaNgAskhan Normal 
ElEcTabuzz Electric 
AEROdactyl Rock Flying

This is the program:

p=>(n=[..."PoisonPsychicWaterRockGrassBugNormalElectricFireFightingGhostGroundIceDragonFairyFlyingSteel".match(/.[a-z]+/g)],m=[n,[" "].concat([11,12,15,0,4,2,16,14].map(i=>n[i]))],[0,1].map(j=>m[j][parseInt([6,4,2,0].map(i=>+(p.charCodeAt(i+j)<91)).join(""),2)]).join(" "))

Or more legibly:

t=p=>{n=[..."PoisonPsychicWaterRockGrassBugNormalElectricFireFightingGhostGroundIceDragonFairyFlyingSteel".match(/.[a-z]+/g)]
m=[n,[" "].concat([11,12,15,0,4,2,16,14].map(i=>n[i]))]
return[0,1].map(j=>m[j][parseInt([6,4,2,0].map(i=>+(p.charCodeAt(i+j)<91)).join(""),2)]).join(" ")}
  • I wrote some other code to help find which type tuples to flip such that the number of types on each side becomes smaller than a power of two, which I didn't achieve on the secondaries: there are 15 first types and 9 second types. The list above reflects that order.
  • I also had a program work out the order of types on the lookup lists based on their appearance in the list of pokémon sorted by name length (the above one), since you can store less bits in the casing of shorter names.

This all might not be optimal, since for example, it does not prioritize keeping the set of types used for short-name-pokémon small over doing it generally for all pokémon, and generally isn't some rigorous thing with a binary tree in it. That approximately 60-80 line piece of code is also useful for testing. Should I add it?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – MTN
    Sep 12, 2023 at 17:27
  • \$\begingroup\$ I downvoted this at first because I thought it was cheating, but upon closer inspection, it seems that this is a very clever reading of the letter of the rules and completely valid. +1 from me! \$\endgroup\$
    – DJMcMayhem
    Sep 12, 2023 at 19:31
6
\$\begingroup\$

Charcoal, 496 400 bytes, score 400

EΦE⪪”}⊞λ⪫¡↥↙vQ�≡⧴ï\`⊕B◨V~R&‖7≔NPv,BJ?…u“κo=B)↘ⅉ⁶2∧M÷5№?m⁹U↑O∕№f}B≡MD|“⧴{x⁼⮌≦3GE⁷℅64↑jEo0ºBjUQ|ÞU⪪↗↘↨→ξ¡Y➙F◧À⎚≔ eω↗3⎇ητ>ⅉ↓ρηX∧"⟧Φζ⊘Q←R]BLHfδ>@J%>;⊖Uf3‽ρIV⭆W↧UZW!⎚H#o?ⅈ8avdQTL^¶¶E◨¹…&5⌕¹WⅉJ"UR«³:⟧⭆·⎚↧ns?;⟧*≡↖,)k⁺⁴WF e´ζwE▶L⍘τ±ïχD↶~A≡1⁶OSkJ^\ωη▷¶«"³AH;_W↷q%⟧‹➙⦃λZ›⊞'≡&B↔⧴↧⭆⊖MU?κL«8▷IZ⁶1Σ:1w▷U›W{L⁵№sΦπ⁸σIPH{:κ/ï\À!e⟦Y�PM⦃¶W.ξ3ζXVLsKL⟲PUoOψI;▶~w∕X3⊙,Sp✳v⊙⎇αkμZτ-ε:ν&[÷c⁰L¡⁴M.ω±YuTZ+)7≕⊖“B?Lec{”¶⪪ι ⊙ι№θλ⊟ι

Try it online! Link is to verbose version of code. Outputs the types in alphabetical order. Explanation: The compressed string contains a list of all the unique prefixes for a given type followed by that type. These are then filtered for the prefixes that match the input string and then the types are extracted.

Previous 496 byte solution outputs the types in the order given in the question:

≔⪪”↶37₂?γ"Π⎚«ζ∨↖↘o*&J›7M‽ ±pλ⁹MgΠf⊟V³!P¹y⁰κ⊘X⮌GQ⟧÷±X´VkGº↗DZwG³↘»§/V↑X″ypLKνN^I→λ↶” υ⭆⪪”}∨D¤Y1H∧2gW±²&JψAχ∕ κ2⊕m⁴η;δKE↘L⎚▷μ²θ[⌈J_;$⁼σ⊗}/¶C~Mv?"V↗7{<|´0⁹ï8'➙1≡⦃Iü◨Rqp⍘td‴⁼xYHïω⪫ψ PρRN:ζg↖Bï↑⪪ÀMmP;e″=y﹪⌊κAλ&↗↔ςJβ~‹τ¿�λ▶⊘Þ?{↥⊙↓⁷_G;›D⁸⦃℅⁹τωx➙UXVςυ;FZ@ºηW⸿⟦EI∕-↗Th_pEGOχ3↷⁻@ε∕Πg⸿“ΣA«CKL↙⁵O>?¤↷⊗KP⊘B{℅&:≕Xe↑HN⧴↖η‴El¡4hw⁻¬×�⍘~o⊕δ~⊕”¶⎇∧ι⊙⪪ι №θλ§υκω⭆⪪”}∧αf.M‴%iI»⁷⁰τ➙:⁼\p'↥'�fP{Pζ⊖№ ↑″⟲σfH940⁵êYS↙Y«9≕%Sm↙⁶|π✳σqD⟦➙γ[Z₂›1⊖0@⊕S6←ψqP⎇›w\;MW;5K⌕Yυλ³⁴↓↷◧T(gB±Wï…↙↖iº÷τ⎇≔2Φ←nYρa¤←⊕ê⪪vK∕Z.8Z73×ζ⊞”¶⎇⊙⪪ι №θλ⁺/§υκω

Try it online! Link is to verbose version of code. Explanation: Starts off by getting a list of all of the types, then works through all of the unique prefixes for each type, outputting the types for which the input contains those prefixes. The verbose code was generated by a program so it's probably not the optimal approach.

\$\endgroup\$
4
  • \$\begingroup\$ Dratini is a Dragon type, without Dragon as a prefix, and so gives no output. \$\endgroup\$ Sep 12, 2023 at 13:05
  • \$\begingroup\$ @DominicvanEssen Thanks for reminding me, fixed now. \$\endgroup\$
    – Neil
    Sep 12, 2023 at 13:22
  • \$\begingroup\$ How does Charcoal achieve such a good compression? The long string has 699 characters (I think), which even if ignoring case & encoded in base-28 (26 letters + space + newline) needs 699*log(28)/log(256) = 420 bytes. What's the trick? \$\endgroup\$ Sep 12, 2023 at 14:35
  • \$\begingroup\$ @DominicvanEssen Charcoal has six different compression routines. In this case it's using LZMA. (The downside of course is the extra byte used to choose between compression routines.) \$\endgroup\$
    – Neil
    Sep 12, 2023 at 16:17
5
\$\begingroup\$

Python 3, 584 bytes

s="lambda s:['4C,sir1e8.!x7l1ew#az#z+rm*br1*H%-t%0rti$5l,x+.0J%#4tt+c%!dos#ni8b(!T7l#ld#iw#tl778V,y6*K*g*H2Kr#s%#3ar#D2tc#d&#4ku#ed#eno$Steel!/!on76q#g8ow6k*Di&!T+id2z*Ek1u#f*rb2Gr*b(0L6y#w&#Ghost!H,G,en&#5p#s6u#V*d*Gl$Electric!pd#hu#El#J2V2/-ud#Gr6l+On#h%#Fire!iz1o$3v#uf#sk#yg#P7n1e2Di8ns+ur2L*R(-bu8Om$Fairy!uf1*fa$Fighting!wr1ac#H*nk#Pr$Dragon!Dra'])or['Fire']"
for i in"8t#97+S96,o95Grass!e94Bug!93Normal!e92o#91#M90#Ice!9/gn$Ground9.Pa$Psychic9-#Rock!9,a#9+e#9*i#9(at$Water9&g$Poison9%y$Flying9$'])+['9#','9!']*any(i in s for i in['".split('9'):s=s.replace(i[0],i[1:])
f=eval(s)

Try it online!

The code decompresses into this:

lambda s:
  ['Bug'               ] * any(i in s for i in [ 'Ca' ,'sir','Met','Pa'                                                             ])
 +['Psychic'           ] * any(i in s for i in [ 'xe' ,'Sl' ,'Mew','az','ze' ,'rmi','br' ,'Mi' ,'Hy'                                ])
 +['Flying',  'Rock'   ] * any(i in s for i in [ 'ty'                                                                               ])
 +['Flying',  'Ice'    ] * any(i in s for i in [ 'rti'                                                                              ])
 +['Grass'             ] * any(i in s for i in [ 'ela','xe' ,'Pa'                                                                   ])
 +['Psychic', 'Ice'    ] * any(i in s for i in [ 'Jy'                                                                               ])
 +['Flying',  'Bug'    ] * any(i in s for i in [ 'tte','cy'                                                                         ])
 +['Flying'            ] * any(i in s for i in [ 'dos','nit','bat'                                                                  ])
 +['Water'             ] * any(i in s for i in [ 'Te' ,'Sl' ,'ld' ,'iw','tle','Se' ,'St' ,'Va' ,'ya' ,'oi' ,'Ki','gi','Ho','Kr','sy'])
 +['Flying',  'Normal' ] * any(i in s for i in [ 'ear','Do' ,'tc' ,'dg'                                                             ])
 +['Poison',  'Bug'    ] * any(i in s for i in [ 'ku' ,'ed' ,'eno'                                                                  ])
 +['Steel'             ] * any(i in s for i in [ 'gn'                                                                               ])
 +['Ground'            ] * any(i in s for i in [ 'one','Sa' ,'oq' ,'gt','owa','oki','Dig'                                           ])
 +['Poison'            ] * any(i in s for i in [ 'Te' ,'ido','zi' ,'Ek','Mu' ,'fi' ,'rbo','Gri','bat'                               ])
 +['Water',   'Ice'    ] * any(i in s for i in [ 'La' ,'oy' ,'wg'                                                                   ])
 +['Poison',  'Ghost'  ] * any(i in s for i in [ 'Ha' ,'Ga' ,'eng'                                                                  ])
 +['Poison',  'Grass'  ] * any(i in s for i in [ 'ep' ,'sa' ,'ou' ,'Vi','di' ,'Gl'                                                  ])
 +['Electric'          ] * any(i in s for i in [ 'pd' ,'hu' ,'El' ,'Jo','Vo' ,'gn'                                                  ])
 +['Ground',  'Rock'   ] * any(i in s for i in [ 'ud' ,'Gra','ole','On','hy'                                                        ])
 +['Flying',  'Fire'   ] * any(i in s for i in [ 'iz' ,'Mo'                                                                         ])
 +['Normal'            ] * any(i in s for i in [ 'ev' ,'uf' ,'kha','yg','Pe' ,'Sn' ,'Meo','Dit','nse','uro','Li','Rat'              ])
 +['Water',   'Rock'   ] * any(i in s for i in [ 'but','Om'                                                                         ])
 +['Fairy'             ] * any(i in s for i in [ 'uf' ,'Mi' ,'fa'                                                                   ])
 +['Fighting'          ] * any(i in s for i in [ 'wr' ,'Mac','Hi' ,'nk','Pr'                                                        ])
 +['Dragon'            ] * any(i in s for i in [ 'Dra'                                                                              ])
 or['Fire']
\$\endgroup\$
2
  • \$\begingroup\$ Why not check against ' for Farfetch'd and . for Mr. Mime? Is it more expensive after compressing? \$\endgroup\$
    – Value Ink
    Sep 12, 2023 at 22:36
  • \$\begingroup\$ @ValueInk Checking against ' messes up the compression algorithm (it's too stupid to deal with it correctly), and checking for . is worse because ','M and i',' both get compressed to single characters, making Mi free compared to . using a character. \$\endgroup\$
    – gsitcia
    Sep 13, 2023 at 0:07
5
\$\begingroup\$

JavaScript (Node.js), score = 566 (566 bytes, 100%)

-6 bytes because 3 Pokemons actually contain their types in their names (and other simplifications)

Even if a way has been found to answer this question by "encoding" the types in the casing of an arranged Pokedex, i tried to achieve 100% accuracy without using this trick while trying to outgolf the other 100% classic Javascript answer, and it turned out pretty well :)

The input is the name of the Pokemon in lower case. The output are the corresponding types, with only the first character uppercased, and multiple types are separated by a space. There is also a trailing space if that's acceptable.

s=>`NormalDgAttIcaEarUfWthIaFeDodTuNseSkTauDitEvYgSn_BugRpiMetFrEdKuPaScEnoIns_GrassSauDdGloEpPaLsViExTan_RockUdAvOleNixOmaRhKabAe_WaterRtlOiPsLdIwTenSloSeaSeeWgOyKrNglOmaStaKabGiGyLapVa_GhostStlHauGen_PoisonSauEdKuEkArbNidBaDdOoViVenLsWeNtGriMuStlGenKo_FireHarVuEsWlRcPonRapGmFl_IceWgOyJyLapRti_DragonTin_ElectricHuGnVoLecJoPd_FlyingIzRfDgEarBatDodScDosAeRtiLtrNit_GroundDsOqDokDigGtUdAvOleNixCubOwaRh_FightingNkPriWrTmMac_PsychicBrAzSloWzPnExRmiJyMrMew_FairyEfUfMr_SteelGn`.split`_`.map(t=>(r=t.match(/.[a-z]+/g)).find(e=>RegExp(e,'i').test(s))?r[0]+" ":"").join``

Try it online!


A little explanation:
Every type is accompanied by a list of strings, that are as short as possible (2 to 4 characters) and that matches any part (ignoring the case) of the highest possible (when useful) number of corresponding Pokemons, unambiguously.
Dual types are achieved by matching the 2 types separately.

The casing in the long string is used to delimit the beginning of each value.

I did the long string by hand, but i think that this is the shortest possible combination.

I don't know of an official golfing way to compress the long string, so i tried to develop a custom program (by using 6 bits instead of 7 to store each "character", because the ASCII values of the long string are all comprised between 65 and 122), but sadly the gain in bytes was inferior to the length of my custom decompression code (a hundred bytes), so i gave up on the compression.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 57 bytes, accuracy 148/150, score ≈ 58.5509

e€ØaḄḃW¹?⁴UÄị“Ɓ[0ḲTọŻZ4⁹ɗrƑkṭkẏḳoḂʠCṂtɠØƭ⁴Ṡ¬ỤþV⁶Ḳ¥;0ḥȧ»Ḳ¤

Try it online!

A monadic link that takes a string argument and returns a list of strings. Taking inspiration from @JanH’s Javascript answer, this relies on the wording of the question that states that the casing of input and output can be specified in the answer. As such, this answer expects the input to be one of the following Pokémon:

BULBaSAuR
IVySAuR
VENuSAuR
CHARMAnDER
CHARMElEON
CHaRIZaRD
SQUIrTle
WARTOrTle
BLASToIse
CATERPIe
METAPOd
BUTTerFREe
wEEDLe
kAKUNa
BEeDRILl
PiDgEY
PIDGeOtTO
PIdGeOT
RATTaTa
RATICaTe
SPeArOW
FeArOW
EKAns
ARBok
PIKAchu
RAIchu
SANDShREw
SANDSlASh
NIDORan
NIDORIna
NIdoQUEen
NIDORan
NIDORIno
NidOKIng
CLEFaiRy
CLEFabLe
VUlPIX
NINETaLES
JIgGLYPuFf
WIgGLYTuFf
zUBat
GoLBat
OdDIsH
gLOoM
VILEpLUmE
pARAs
PARaSECt
VeNONAt
VEnOMOTh
DIGlETt
DUGtRIo
MEOwTh
PERSiAn
PSYdUck
GOLdUck
MAnkey
PRIMeape
GROWLiTHE
ARCAnINE
POLiWag
POLIWhIrl
POlIWrAth
ABRA
KADABRA
ALAKAZAM
MAchop
MAChoke
MAChamp
BELLSpROuT
WEEPInBElL
VICTReEBeL
TeNTACOol
TEnTACRUel
GEodUDe
GRAveLEr
goLEm
POnYTA
RAPIdASH
SloWpOke
slOwBro
MAgneMite
MagnEton
FARFEtCh'D
dOdUO
DoDrIO
sEel
DEwgOng
GRIMer
Muk
SHELlDer
CLOysTer
gaSTly
HauNTer
geNGar
oNIx
DROWZEE
HYPNO
KRaBby
KINgLer
VOLTorb
ELECTRode
ExeggCUtE
ExeggUToR
CUbONe
MARoWAk
HITMOnlee
HITMONchan
LICKITuNg
KOFFIng
WEEZIng
RHyhORn
RhyDOn
CHANsEy
TANGElA
KANGASKhAn
HOrSea
SEaDra
GOLdEen
SEAkIng
STaRyu
stArMie
Mr. miMe
ScyTHEr
jyNX
ELECTABuzz
MAgMAR
PINSIr
TAUrOs
MAGIkArp
GyarAdOS
LapRas
DItTo
EEvEe
VAPOrEon
JOLTeon
FLArEON
PORYgOn
OManYtE
OMasTaR
KabUtO
KAButOpS
AERodACtYL
SNORlAx
aRTICuNO
zaPdOS
mOLTrES
DRaTINI
DRAGoNAIR
DraGONiTE
MEWTWO
MEW

The casing of the Pokémon encodes a binary number. If this number is non-zero it is interpreted as a bijective base-16 number. This is then reversed, cumulative summed and then looked up into the list of powers. Zero matches the last power in the list, psychic. The powers are lower-case except for grass and ice which are title case, since as @ais523 discovered this gives the shortest compressed string. The precise compressed string here is different because of the different algorithm used.

The two missed ones relate to four-letter double-power ones that are too short to encode their power in the casing.

Detailed explanation

eۯa               | For each character, check whether it is a lowercase letter
    Ḅ              | Convert from binary
       ¹?          | If non-zero:
     ḃ   ⁴         | - Then convert to bijective base 16
      W            | - Else wrap in a list
          U        | Reverse list
           Ä       | Cumulative sum
            ị“…»Ḳ¤ | Index into compressed string split at spaces

Verification of accuracy

\$\endgroup\$
2
  • \$\begingroup\$ What is the purpose of the convoluted number to type algorithm? Bijective numbering only seems to be better than normal when you control the length, which you don't, right? Is it just because it's a built-in? \$\endgroup\$
    – jan
    Oct 10, 2023 at 21:48
  • \$\begingroup\$ @JanH in this situation I wanted to keep the overall base to 16 (both to minimise the number of letters needed and to allow use of the ). However, I needed to allow for 17 types (albeit one never appears in its own). The use of the ? to handle zero specially allowed for all of the base types to be captured with a single digit between 0 and 16, with the composite types having two objective digits, the first type and the increment needed for the second type. As you say, bijective base conversion is a built in anyway. \$\endgroup\$ Oct 10, 2023 at 22:49
1
\$\begingroup\$

Python 3, 888 Bytes, Accuracy 86/150, Score 1200

score is 1200.64... but that doesn't matter. Here's my pitiful attempt:

s="{'GasPs:BarIsrVsOiGomVpeBpWnVe,Fr:CaCeVpNtsGleAnPyRdMmFrn,FrFi:CidMts,Wtr:SrWoeBtePdkGdkPigPwlSeSlKbKgrHsSdGdnSkgSrMkVr,Bug:CrMadPs,BugFi:BrStr,BugPs:WdKuBrVotVm,FiNm:PgPeoPgtSawFrFtDdoDr,Nm:RtaRcMwPsnLigCnyKsTrDtoEvePynSrx,Ps:EasAbkNonNrNrGmMukKfgWzg,Et:PauRcVtbEteEaJtn,Gu:SswSshDltDtoCoMok,GuPs:NqnNk,Fiy:CaCa,FiyNm:JyWy,FiPs:ZbtGb,BugGas:PrsPs,Ft:MkPeMhMheMhpHoeHn,FtWtr:Pwh,Pcc:ArKaaAaDweHpoMtMew,PsWtr:TalTc,GuRc:GdeGeGlmOiRhnRd,PccWtr:SpSwoSre,EtSel:MeeMe,IceWtr:DggCsLr,GotPs:GtHnrGg,GasPcc:EgeEgr,Gas:Tga,FiyPcc:MM,IcePcc:Jn,FiWtr:Ga,RcWtr:OneOsrKuKt,FiRc:Aa,FiIce:Ac,EtFi:Zd,Dg:DtiDor,DgFi:Doe'}"
for i in ",', '",":': '":s=s.replace(i[0],i[1:])
d=eval(s);h=lambda x:x[::len(x)//2]
def f(s):r=[k for k in d if h(s)in d[k]][0];return[i for i in "Bug Dragon Electric Fairy Fighting Fire Flying Ghost Grass Ground Ice Normal Poison Psychic Rock Steel Water".split() if h(i)in r]

Uses the fact that the s[::len(s)//2] subset is pretty darn good for uniqueness, for both names and types. Stores everything in a big honking compressed dict, and fails to be good.

\$\endgroup\$
0
\$\begingroup\$

Python 2, 1022 bytes, 100%

I generated a hash of each name and only recorded the unique first characters, then for the types I used bitwise operations.

It didn't work as well as I'd have hoped but here's my attempt anyway:

import zlib,base64,hashlib;d=lambda x:zlib.decompress(base64.b64decode(x)).split();h=d('eJwdkcsBBCEMQlt5JaiJv3LUaP8lLLMHnEQHhLjSoHfWJXawUsUTMQknjNYPxan2KI2XjFI4HXMd70aMyvtOXhfUH1EK85GdnYqEo1AHzRa1f1u6ri6uiOaLojI4L7iPLU5FsttwPzyR4pEyyZHPNKlyM/zpq8tiMwulMo7+Twzt25W2MLkm3cw6R5BQDFl9wsWy2kZLEr/I8NtbywwF6szDvKg5l5ap0mqVJls74lsWivry5mbNxMmHqyz7uuK+TdMUQrxQ1IFNKTszcTJT+a4qkZJIf0KSpsaXjaV+yZZzti5x+qar0On4PE6sUcyFhNXLOQNvjLTwgmfNZmtspp3O0Gvp4d7Tk33xJHRZkz7Y+QpHEHFLqoiheZ1AQZrNH4nfgPQ=');n=d('eJxNUYkNAyEMWyUjhHzQ/Rdr7EBV6STAefycyVILMQlx21vF8gxUjWbde2bMc5usEhePPkMVgGMexVgagkfPhidb0d2QxkeWFy7nLmHHa7tshbW9wBu00wsXLg/GLGEA/WWXuNkUjNPeWpsHpTHkY2G/ylIJHQw7s34a5kSh6S3+tMJoXJlPCHD/2C+VEz0V4KOahY7rj/25i+G+oJEN9xlM0bFCGJ51Qx5H45sixihAnxSaxmnOm5c67MzPYaSYdFI/t0MMk8dNLw8y4iSxyVL8C+8IYSA=');f=lambda x:','.join(v for i,v in enumerate('Grass Poison Fire Flying Water Bug Normal Electric Ground Fairy Fighting Psychic Rock Steel Ice Ghost Dragon'.split())if 2**i&next(int(v)for k,v in zip(h,n)if hashlib.md5(x).hexdigest()[:len(k)]==k))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.