Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given an input of a string consisting of any message from our site chatroom taken from the list described and linked below, output either a truthy or a falsy value attempting to predict whether that message was starred or not in 50 bytes or less.

You may use any truthy or falsy values, but they must be identical (i.e. there should only be two possible outputs, one truthy and one falsy). The input will be given as raw HTML with newlines removed, and it may contain non-ASCII Unicode characters. If you require input in something other than UTF-8, please say so in your answer.

The winning submission to this challenge will be the one that predicts the highest percentage of chat messages correctly, out of the list linked below. If two given submissions have the same success rate, the shorter submission will win.

Please provide instructions for running your code on the entire set of messages and calculating the percentage correct. Ideally, this should be a bit of boilerplate code (not counted towards your 50 bytes) that loops through the positive test cases and outputs how many of them your code got correct and then does the same for the negative test cases. (The overall score can then be calculated manually via (correctPositive + correctNegative) / totalMessages.)

So that your code is reasonably testable, it must complete in 5 minutes or less for the entire list of chat messages on reasonable modern-day hardware.

The full list of chat messages can be found here, and it consists of the 1000 latest starred messages as truthy test cases and the 1000 latest unstarred messages as falsy test cases. Note that there are two files in the gist; scroll about halfway down for the unstarred messages.

share|improve this question
3  
Knowing the behaviors of chat, I think the following Pyth would suffice: O2 – A Nerd - I Jan 17 at 22:18
8  
Considering the history of past starred messages, Regex, 11 bytes: Don'?t star – Downgoat Jan 17 at 22:26
10  
This would be much easier if you were also given the user as part of the input. – Mama Fun Roll Jan 18 at 1:07
3  
At some point I would've answered Regex, 2 bytes \^ – Pietu1998 Jan 18 at 8:46
12  
I think you should run this again on the next 1,000 messages, and see which one really predicted starredness – abligh Jan 18 at 23:03
up vote 25 down vote accepted

Retina, 50 bytes, 71.8% 72.15%

^.*([[CE;ಠ-ﭏ]|tar|ol|l.x|eo|a.u|pin|nu|o.f|"$)

Tried some regex golfing at @MartinBüttner's suggestion. This matches 704 starred messages and doesn't match 739 unstarred messages.

The ^.*( ... ) is to make sure that there is always either 0 or 1 match, since Retina outputs the number of matches by default. You can score the program on the input files by prepending m` for multiline mode, then running

Retina stars.retina < starred.txt

and likewise for unstarred.txt.


Analysis / explanation

I generated the above snippets (and many more) using a program, then selected the ones I wanted manually. Here's some intuition as to why the above snippets work:

  • C: Matches PPCG, @CᴏɴᴏʀO'Bʀɪᴇɴ
  • E: Matches @ETHproductions, @El'endiaStarman
  • ;: Because the test cases are HTML, this matches &lt; and &gt;
  • ಠ-ﭏ: Matches a range of Unicode characters, most prominently for ಠ_ಠ and @Doorknob冰
  • tar: Matches variations of star, @El'endiaStarman (again) and also gravatar which appears in the oneboxes posted by new posts bots
  • ol: Matches rel="nofollow" which is in a lot of links and oneboxes
  • l.x: Matches @AlexA., @trichoplax
  • eo: Mainly matches people, but also three cases for @Geobits
  • a.u: Mainly matches graduation, status, feature and abuse
  • pin: Matches ping and words ending in ping. Also matches a few posts in a discussion about pineapple, as an example of overfitting.
  • nu: Matches a mixed bag of words, the most common of which is number
  • o.f: Matches golf, conf(irm|use)
  • "$: Matches a double quote as a last character, e.g. @phase He means "Jenga."

The [ is nothing special - I just had a character left over so I figured I could use it to match one more case.

share|improve this answer
    
(I haven't posted the testing code yet because it seems to be running rather slowly, and I'd like to figure out why. It's too late now though.) – Sp3000 Jan 18 at 14:41
1  
Executing Retina once for each test case will take a long time. Multi-line mode reports the claimed score pretty much instantly. – Dennis Jan 19 at 23:32
    
@Dennis Thanks, I completely forgot I could do that. – Sp3000 Jan 20 at 9:50
1  
LOL, now my name is a star magnet? – ETHproductions Jan 28 at 20:56

JavaScript ES6, 50 bytes, 71.10%

Correctly identifies 670 starred and 752 non-starred.

x=>/ .[DERv]|tar|a.u|l.x|<i|eo|ol|[C;ಠ]/.test(x)

Now across the 70% barrier, and beating everyone except Retina!

Returns true if the message contains any of these things:

  • A word of which the second letter is D, E, R, or v;
  • tar (usually star);
  • a and u with one char in between;
  • l and x with one char in between (usually alex);
  • italic text;
  • eo or ol;
  • a C, a semicolon, or a .

Here's a few more fruitful matches that don't seem to be worth getting rid of others:

  • nf
  • nu
  • yp
  • n.m

This has been growing closer and closer to the Retina answer, but I have found most of the improvements on my own.

Test it out in the console of one of these pages: star texts, no-star texts

var r=document.body.textContent.replace(/\n<br/g,"<br").split("\n").slice(0,-1);
var s=r.filter(function(x){return/ .[DERv]|tar|a.u|l.x|<i|eo|ol|[C;ಠ]/.test(x)}).length;
console.log("Total:",r.length,"Matched:",s,"Not matched:",r.length-s);

Here's an alternate version. /a/.test is technically a function, but doesn't satisfy our criteria:

/ .[ERv]|a.u|l.x|<i|eo|yp|ol|nf|tar|[C;ÿ-ff]/.test

This scores 71.90% (697 starred, 741 unstarred).


I've been running some analyses on the lists to see which regex groups match the most starred and the least unstarred posts. The analyses can be found in this Gist. So far, I've checked aa and a.a matches. a.u is down at around #50 with a score of 28, yet it's the most efficient match of its format...

share|improve this answer
    
There are only 1000 messages...? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 17 at 22:40
2  
@CᴏɴᴏʀO'Bʀɪᴇɴ Some were multi-line, which wasn't accounted for in the snippet. This has been fixed. – ETHproductions Jan 17 at 22:50
    
Why no one uses /regexp/.test()? I think it's possible to squeeze in a few more cases with that. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jan 18 at 2:36
7  
Today I learned I can get chat stars just by saying my own name. – Alex A. Jan 18 at 2:40
    
@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Thanks, dunno how I didn't think of that – ETHproductions Jan 18 at 2:43

Pyth, 50 bytes, 67.9 %

0000000: 21 40 6a 43 22 03 91 5d d3 c3 84 d5 5c df 46 69 b5 9d  !@jC"..]....\.Fi..
0000012: 42 9a 75 fa 74 71 d9 c1 79 1d e7 5d fc 25 24 63 f8 bd  B.u.tq..y..].%$c..
0000024: 1d 53 45 14 d7 d3 31 66 5f e8 22 32 43 7a              .SE...1f_."2Cz

This hashes the input in one of 322 buckets and chooses the Boolean depending on that bucket.

Scoring

$ xxd -c 18 -g 1 startest.pyth
0000000: 72 53 6d 21 40 6a 43 22 03 91 5d d3 c3 84 d5 5c df 46  rSm!@jC"..]....\.F
0000012: 69 b5 9d 42 9a 75 fa 74 71 d9 c1 79 1d e7 5d fc 25 24  i..B.u.tq..y..].%$
0000024: 63 f8 bd 1d 53 45 14 d7 d3 31 66 5f e8 22 32 43 64 2e  c...SE...1f_."2Cd.
0000036: 7a 38                                                  z8
$ echo $LANG
en_US
$ pyth/pyth.py startest.pyth < starred.txt
[[345, False], [655, True]]
$ pyth/pyth.py startest.pyth < unstarred.txt
[[703, False], [297, True]]
share|improve this answer

CJam, 45 bytes, 65.55%

l_c"\"#&'(-.19<CEFHIJLMOPSTXY[_qಠ"e=\1b8672>|

This checks if the first character is in a specific list or the sum of all code points is larger than 8,672.

Scoring

$ cat startest.cjam
1e3{l_c"\"#&'(-.19<CEFHIJLMOPSTXY[_qಠ"e=\1b8672>|}*
$ java -jar cjam-0.6.5.jar startest.cjam < starred.txt | fold -1 | sort | uniq -c
    308 0
    692 1
$ java -jar cjam-0.6.5.jar startest.cjam < unstarred.txt | fold -1 | sort | uniq -c
    619 0
    381 1
share|improve this answer
    
+1 for teaching me about the fold command, along with the actual answer. – Doorknob Jan 17 at 23:42

Matlab/Octave, 17 bytes 60.15%

Correctly classifies 490 messages as stared, 713 messages as unstared

Current version:

Just checking the length.

f=@(w)numel(w)>58

Old version:

Could be translated to any other language. It just checks whether the message contains the words star or not. score: 59/911/52.5%

f=@(w)nnz(strfind(lower(w),'star'))>0 %

Results for testcases using this code:

slCharacterEncoding('UTF-8');

fid = fopen('codegolf_starred_messages_starred.txt');
line = fgetl(fid);
starred = 0;
while ischar(line)
    if f(line);
        starred = starred +1;
    end

    disp(line)
    line = fgetl(fid);
end
fclose(fid);


fid = fopen('codegolf_starred_messages_unstarred.txt');
line = fgetl(fid);
unstarred = 0;
while ischar(line)
    if ~f(line);
        unstarred = unstarred +1;
    end

    disp(line)
    line = fgetl(fid);
end
fclose(fid);

disp(['  correctly classified as *ed: ',num2str(starred)])
disp(['correctly classified as un*ed: ',num2str(unstarred)])
disp(['                  total score: ',num2str((starred+unstarred)/20),'\%'])
share|improve this answer

CJam, 32 bytes, Overall score of 0.5605 (56%).

Correctly identifies 428 starred messages and 693 unstarred messages. Total score is (360+730)/2000=0.545.

l_el"sta"/,1>\,)4%!|

Not expecting to win, Ill see how it performs. Above is the code for a single message, to run with multiple use this modified version that returns amount of starred messages:

1000{l_el"star"/,1>\,)6%!|}fA]:+

Just test it with STDIN being the raw text of either file. Returns true if the message contains "star" or if length + 1 mod 4 = 0.

share|improve this answer
2  
So... if four divides one more than the length of a message, then it has a chance of being starred? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 17 at 22:47
2  
@CᴏɴᴏʀO'Bʀɪᴇɴ Yes, but it provides for a high score – GamrCorps Jan 17 at 22:50

Retina, 46 bytes, 68.55

^.*([zj_C;&¡-ff]|sta|san|soc|bo|eo|xk|l.x|<.>)

679 star : 692 unstar

Switched to Retina to get some more regexes in... Still not done.

share|improve this answer
    
Oh yeah, forgot about that. I'll fix it. – Mama Fun Roll Jan 20 at 1:43

JavaScript ES6, 0.615 = 61.5%

342 correctly identified as starred, 888 correctly identified as unstarred, (342+888)/2000 = 0.615

x=>-~x.search(/(bo|le)x|sta|ಠ|ツ/i)

Test like this on this or this:

r=document.body.innerHTML.replace(/<\/*pre>/g,"").split`
`.filter(x=>-~x.search`(bo|le)x|sta|ಠ|ツ`).length

I STILL MIGHT GET YOU, MY PRETTY!

share|improve this answer
1  
I've got you now ;) – ETHproductions Jan 17 at 23:27
    
@ETHproductions GG. I'll look for some more common patterns. – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 17 at 23:30

C# 6.0 (.NET Framework 4.6), 50 Bytes, 63,60%

bool s(string i)=>Regex.IsMatch(i,"ol|tar|l.x|ಠ");

Program i used for testing purposes:

void Main()
{
    var starred = @"C:\starred.txt";
    var unstarred = @"C:\unstarred.txt";

    var linesStarred = File.ReadAllLines(starred);
    var linesUnstarred = File.ReadAllLines(unstarred);

    var cls = linesStarred.Count();
    var clsc = 0;

    foreach (var line in linesStarred)
    {
        if ( s(line) ) clsc++;
    }

    var clu = linesUnstarred.Count();
    var cluc = 0;

    foreach (var line in linesUnstarred)
    {
        if (!s(line)) cluc++;
    }

    $"Starred {clsc}/{cls} correct ({(clsc/cls*100):0.00}%)".Dump();
    $"Unstarred {cluc}/{clu} correct ({(cluc /clu*100):0.00}%)".Dump();
    $"{(((clsc+cluc)/(decimal)(cls+clu))*100):0.00}".Dump();
}

bool s(string i)=>Regex.IsMatch(i,"ol|tar|l.x|ಠ");
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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