14
\$\begingroup\$

Try it online! currently has 680 listed languages, all of which are searchable. For most of those languages, when searching for it, you don't have to enter the entire string. For example, entering lega results in just 05AB1E (legacy) appearing, and entering d+ results in only Add++. However, for some languages, there is no such string that results in only that languages, e.g. Jelly returns both Jelly and Jellyfish

We will call the length of the shortest string required to return only a specific language on TIO the TIO uniqueness of that language. The TIO uniqueness of a language for which this is impossible is undefined. Note that TIO ignores case when searching, so bri results in Brian & Chuck and SOM results in Somme.

You are to take the name of a programming language on Try it online!, exactly as spelt in the search function, and return that language's TIO uniqueness. If the language's TIO uniqueness is undefined, you may instead return any value which is not a positive integer (or could reasonably be interpreted as a positive integer). This value need not be consistent between such languages. Your program should handle all 680 languages currently on TIO.

This is , so the shortest code wins. Standard loopholes are forbidden, especially internet access. You may also not access the file system of TIO. Essentially, your program should work whether it's run on TIO or locally.

Test cases

All test cases include the TIO uniqueness string in lowercase, as TIO is case insensitive in its search, and use 0 for undefined TIO uniquenesses

"Arcyóu" -> 1 ("ó")
"Befunge-98 (PyFunge)" -> 13 ("befunge-98 (p")
"Cauliflower" -> 3 ("cau")
"Shove" -> 3 ("hov")
"Funky" -> 0
",,," -> 2 (",,")
"Agony" -> 0
"Starry" -> 4 ("tarr")
"Add++" -> 2 ("d+")
"ATS2" -> 3 ("ts2")
"F# (.NET Core)" -> 5 ("f# (.")
"Dyvil" -> 2 ("yv")
"Python 3.8 (pre-release)" -> 2 ("3.")

The full list of names and the full list of test cases

\$\endgroup\$
4
  • \$\begingroup\$ Internet access is forbidden, but if our code runs on TIO, can we look at the files on the virtual disk? \$\endgroup\$ – Adám Mar 30 at 23:39
  • 2
    \$\begingroup\$ @Adám I'm going to say no, as the aim is (partially) to compress the strings/substrings of the languages \$\endgroup\$ – caird coinheringaahing Mar 30 at 23:39
  • \$\begingroup\$ "If the language's TIO uniqueness is undefined, you may instead return any value which is not a positive integer if you wish." Does this mean we have other choices? If so, what are they? \$\endgroup\$ – Delfad0r Mar 30 at 23:48
  • \$\begingroup\$ @Delfad0r It means that, so long as the output is not a positive integer (or that it isn't anything that could reasonably be construed as a positive integer, say the string "1" instead of 1), it's fine to be output when the TIO uniqueness is undefined \$\endgroup\$ – caird coinheringaahing Mar 30 at 23:51
17
\$\begingroup\$

JavaScript (Node.js),  819  779 bytes

Returns 0 for undefined TIO uniqueness.

s=>(B=Buffer)('J .!> . 8 " .  . 0 L"0"c$E"~~~="8"~1 Y$^"~~~j S$x"P S$;"7 @ Z G"/$8$A :%X!T%A G M$c*h"d"L!Q$8"~F$.$>"s$@"`"E 3 1$r"U">"8 F&~Y"="z"~Q"F"E"g |"R%m!c$"~N"~?$Q  1 ~W B$k"F ="d$> U"7%"""F"X%Y%s"S$E"<-O$b _"]"?$3 <$B i"0"~A"W">$6 L `"I%2"1"?$6"M "A _$2"A ="; T"t @$:"q"N i"["V&~= z"5"1 I!N"8"Z ` ~~B 4"1 }"#"2$."e P F ;!A"W$K G">$9$K"T M*W #"8 < 0"A ]""~~J Z""m"0"V!; ~~[ h+$2$~^"1"3$1"3 A$}"D"~i"9 H%N"~3 9 K"~4"; C%C"Q"3"/ X ^"D"9$4 4 /"7 J":$$0*o"~<"Z 9"T"I"~D$5"@ 1"j ". ~c"O$4"3 O ~X 6$K"I ~8 F  d$T } 6"#"V"W";$I$0 H$R"x$"[$6 j i"U"~M L"K$~~h W$L O"0%="Z 4"F$X"6!?$;"4"M"~0$~1%r"k"6"K"^"2 5$V v"4"J"z 1"1 H$;$W"#">!i"."V"V$e"6$~~<*~C!~/"7 8!/ q$3"U /"."? t"Y"J!<$4 i"~P K"Y'.replace(/[.-~]/g,c=>'#'.repeat(B(c)[p=0]-44))[B(s).map(c=>p=(p*79^c)>>>0)|p%12635])[0]-32

Try it online! (test cases)

Try it online! (all languages)

How?

There are only \$10\$ distinct TIO uniqueness values, ranging from \$0\$ to \$13\$. Besides, more than 50% of the languages have a TIO uniqueness of \$3\$.

 uniq. | count | ratio
-------+-------+--------
   0   |   97  | 14.24%
   1   |   12  |  1.76%
   2   |  140  | 20.56%
   3   |  357  | 52.42%
   4   |   56  |  8.22%
   5   |   11  |  1.62%
   6   |    2  |  0.29%
  10   |    4  |  0.59%
  11   |    1  |  0.15%
  13   |    1  |  0.15%

We need:

  • a function \$H_0\$ that turns the language name \$s\$ into an integer \$H_0(s)\$
  • a function \$H_1\$ and a corresponding lookup table \$T\$ so that the TIO uniqueness of the language is \$T[H_1(H_0(s))]\$

It seems unlikely to find some simple functions \$H_0\$ and \$H_1\$ that would directly lead to a small lookup table. But if we use \$3\$ (the most common uniqueness) as the padding value for unused slots, the table is going to contain a lot of \$3\$'s.

So our strategy is to use:

  • the first 14 printable ASCII characters (32 to 45, i.e. to -) to encode the actual uniqueness values other than \$3\$
  • all other printable characters (46 to 126, i.e. . to ~) to encode runs of 2 to 82 consecutive \$3\$'s

Conveniently, the single quote ' (ASCII code 39) will never appear in the table because no language has a uniqueness of 7. So we can use it as our string delimiter and safely use " and ` in the table without having to escape them.

We now need to find \$H_0\$ and \$H_1\$ so that the distribution of actual uniqueness values among the \$3\$'s leads to the smallest table with this simple compression scheme.

After some brute-forcing, it turns out that the following functions work reasonably well:

  • Buffer(s).reduce((p, c) => p * 79 ^ c) >>> 0 (actually implemented with a .map())
  • % 12635
\$\endgroup\$
1
  • 4
    \$\begingroup\$ +1, You should write a blog article how to compress strings using hash functions or in other ways \$\endgroup\$ – wasif Mar 31 at 3:48
3
\$\begingroup\$

Haskell, 750 bytes

(("K%J#3#=#5##2'#5#3#L%5#5'2';#J#[%O'%_%8#d#B'70_'%t%7#e%]%7%D%Zq'G#Z3#5#4#e#8%2#<%6#7%9%R%k%9%5)4%>%ZX%u(D'<'@#Zj'3#U%W%2(~'4#]'M'6%R#2#5%<#D%Z%c'U#D#9%I':#a'J$=%ZY%`%2#3%R%3%C-Z_%3%;($I#A%Q%N#G'æ%3'v#d'¨%G#U#E#B'[%>#B%5%7$f%Z3#`'8#ZX'5%6#d%E-Y%r%B#@#;%¶#2#Zl%Ò%f%<%G%q-;'8#Q'k$_%l%[%Z#3'6$7'y#9%¢%N%f#^'>#S#C'2'k%5%o%Z_%F'P#c%;']#Zu'?#6%Zs#a'>#I%I%Į'B#B%B'9%;%2%O%Q#9%]%F%x#?#g#T%N'ª%V%B%j%I#3%M%u%Z3'7#T%%ZW#Ze#5%U%7#V#P#N%D%8#V%9%`(W%W';#g$|%a(5#K#6$3%~##A._#7%M%3#2#5#a%9'C%c%Z%V%V$;#?%#U'2%@$7%<%?%3%ě%G'c'4%J#Y%L#?%8#4%q%B'%K'=%B%L%E#A#9%6(@'D%2(Z[#8-D%V'L'?%i%A'¨%['m(3(@#>$U%M)I(e#5(;%w%J'o%2'T%H%E$[#9$8%8'5%2#=%y%>'k#P%4#?%#>#E%4#ZV'C%4#Q">>=(\i->[i-35|i<49]++([1..i-49]>>[3])).e)!!).foldr(\y a->mod(1323*a+(e y))9960)0
e=fromEnum

Try it online!

After Arnauld added an explanation for his answer, it looks like my answer was just a Haskell port of his. Here are the relevant differences:

  • lenghts from \$0\$ to \$13\$ are encoded with character points \$35\$ to \$48\$, in order to avoid double quotes ";
  • runs of consecutives \$3\$'s are encoded with character points \$49\$ to \$\infty\$;
  • I used \$1323\$ in \$H_0\$ and \$9960\$ in \$H_1\$ (which should result in a slightly smaller lookup table).
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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