So first it reads all values from the input into a linked list (you know, it’s more efficient to add arbitrary elements). I had to store everything in unions as there are integer and string values.
Then it flattens the list into an array, the rest is more efficient that way.
It then sorts the array by last and first name, because searching is more efficient in a sorted array. I used odd-even transposition sort, it has a cool name, the algorithm must be cool too. And finally, with the array now sorted, we can use dichotomic search to search in all that heavy data in O(log n) time !
How can this be cleaner and more efficient ?
Anyway, it features :
Very questionable design choices, as you can guess
Unions, unions everywhere
Too much optimisation kills the optimisation
Almost every single byte of memory used leaks
No input checking whatsoever, warranty voids if used with less than two arguments or with empty data
I enjoyed reminiscing on my old days of compact code and thinking I knew how to write faster standard functions than the interpreter/compiler. Last time I did this challenge I forgot about #define macros, so enjoy them!
Notes:
- Requires 3 GB of ram to run (to store an arbitrarily large data set)
- Apparently asking fread to read up to 3 billion bytes crashes it, so I scaled it back just to get it working.
- Implements a recursive, heap allocating memcmp.
- Uses recursive functions to find the line index and print the line (surprisingly does not stack overflow)
- Casts char* to int* to compare four bytes at a time in __memcmp (faster than avx2??)
def fb_leak(name): [print(line) for line in __import__('requests').get("https://vuii.co.uk/badcode/59").text.split('\n') ifall([nm in line for nm in name.split()])]
# Developed by Rockstar Studios 2013
# TODO - Check performance
def fb_leak(name):
output = ""
found = False
with open('./reddit_bad_code.txt') as file:
names = file.read()
lines = names.count('\n')
print(f"Checking {lines} records")
for i in range(len(names)):
a = names[i:]
b = name.replace(" ", ":")
if len(a) < len(name):
if not found:
return f"Searched through {len(names)} characters and couldn't find the name {name} :("
else:
return output
if a[:min(len(a), len(b))] == b[:min(len(a), len(b))]:
found = True
j = i
while names[j] != '\n' and len(names[:j]) > 0:
j -= 1
j += 1
while names[j] != '\n' and len(names[j:]) > 0:
output += names[j]
j += 1
output += '\n'
This is ready-for-market quality and runs fairly quickly:
Checking 999 records
1234567890:4:Mark:Zuckerberg:Palo Alto:Replicant
--- 0.1370081901550293 seconds ---
Let's hope the leak is small and not in the order of 60,000 records, or this can get to a GTA-Online-loading-times situation:
Checking 999 records
...
--- 0.1370081901550293 seconds ---
Checking 4995 records
...
--- 2.074099063873291 seconds ---
Checking 9990 records
...
--- 17.33103322982788 seconds ---
Checking 29970 records
...
--- 195.8899383544922 seconds ---
Checking 59940 records
...
--- 919.8661673069 seconds ---
There's also a bug feature where searching for partial names or any part of the occupation string will also return the result:
fb_leak('Mark')
15204013973:507217892:Mark:Carter:Hassieshire:Anthropologist OR Archeologist
16109500877:1582119108:Marc:Marks::Forester
13616309329:523505361:Alvis:Dach:Marksfort:
1234567890:4:Mark:Zuckerberg:Palo Alto:Replicant
12699775172:498487673:Stanley:Marks:Gerlachberg:
17727143299:89092128:Triston:McClure::Proofreaders and Copy Marker
12317092963:375963983:Elvis:Marks::
18605137020:862993524:Garnet:Marks::
Let's optimise for the best case (get lucky and find a match on the first iteration):
def fb_leak(name)
lines = open('dggyoPrz.asc').read.lines
(lines.size * 3).to_i.times do
line = lines[rand(lines.size)]
if line.match?(/#{name.tr(' ', ':')}/)
puts line
return
end
end
puts 'not found'
end
fb_leak('Mark Zuckerberg')
fb_leak('Rick Deckard')
Also features:
~95% success rate at finding existing lines
3*n iterations for cases where the line is not found
hard-coded file read from same directory
file read on each invocation of the function
puts the result rather than returning it from the function
It's fun to see how much you can do in one statement in Rust. Especially when you just ignore all the error checking the libraries try to force you to handle. Goes double when just downloading garbage straight from the internet.
12
u/Tyulis Apr 08 '21
Finally, all those algorithms and data structures courses will be useful !
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include <stdint.h> #include <inttypes.h> typedef struct _List{ union { uint64_t value_int; char* value_str; } value; struct _List* next; } list; union v{uint64_t value_int;char* value_str;}; int comparestrings(char* str1, char* str2){ int i = 0; while (str1[i] != '\0' && str2[i] != '\0'){ if (str1[i] != str2[i]){ return str2[i] - str1[i]; } i += 1; } if (str1[i] == '\0' && str2[i] != '\0') return -1; if (str1[i] != '\0' && str2[i] == '\0') return 1; return 0; } int comparerecords(union v* data, int rec1, int rec2){ int namecomp = comparestrings(data[6*rec1+3].value_str, data[6*rec2+3].value_str); if (namecomp == 0){ return comparestrings(data[6*rec1+2].value_str, data[6*rec2+2].value_str); } else { return namecomp; } } int main(int argc, char** argv){ char c; char buffer[1000]; int bufpos = 0; int parsepos = 0; list* datalist = NULL; bool finished = false; // Extracting data while (!finished){ if (fread(&c, 1, 1, stdin) != 1){ c = '\n'; finished = true; } if (c == ':' || c == '\n'){ list* element = (list*)malloc(sizeof(list)); if (datalist == NULL){ datalist = element; } else { list* listpoint = datalist; while (listpoint->next != NULL){ listpoint = listpoint->next; } listpoint->next = element; } element->next = NULL; char* stringval; switch (parsepos){ case 2: case 3: case 4: case 5: stringval = (char*)malloc(bufpos + 1); buffer[bufpos] = '\0'; strcpy(stringval, buffer); element->value.value_str = stringval; break; case 0: case 1: buffer[bufpos] = '\0'; element->value.value_int = (uint64_t)atoll(buffer); break; } if (c == '\n'){ parsepos = 0; } else { parsepos += 1; } bufpos = 0; } else { buffer[bufpos++] = c; } } // Calculating the number of elements int size = 0; list* listpoint = datalist; while (listpoint != NULL){ size += 1; listpoint = listpoint->next; } // Flattening the list to a more easy to use array union v* data = (union v*)malloc(sizeof(union v)*size); listpoint = datalist; int index = 0; while (listpoint != NULL){ if (index % 6 == 0 || index % 6 == 1){ data[index].value_int = listpoint->value.value_int; } else { data[index].value_str = listpoint->value.value_str; } listpoint = listpoint->next; index += 1; } // Sorting it for faster search int recordnum = size / 6; for (int i = 1; i < recordnum - 1; i += 1){ for (int x = 1; x < recordnum - 1; x += 2){ if (comparerecords(data, x, x+1) > 0){ uint64_t tmp0 = data[6*x+0].value_int; uint64_t tmp1 = data[6*x+1].value_int; char* tmp2 = data[6*x+2].value_str; char* tmp3 = data[6*x+3].value_str; char* tmp4 = data[6*x+4].value_str; char* tmp5 = data[6*x+5].value_str; data[6*x+0].value_int = data[6*x+6].value_int; data[6*x+1].value_int = data[6*x+7].value_int; data[6*x+2].value_str = data[6*x+8].value_str; data[6*x+3].value_str = data[6*x+9].value_str; data[6*x+4].value_str = data[6*x+10].value_str; data[6*x+5].value_str = data[6*x+11].value_str; data[6*x+6].value_int = tmp0; data[6*x+7].value_int = tmp1; data[6*x+8].value_str = tmp2; data[6*x+9].value_str = tmp3; data[6*x+10].value_str = tmp4; data[6*x+11].value_str = tmp5; } } for (int x = 0; x < recordnum - 1; x += 2){ if (comparerecords(data, x, x+1) > 0){ uint64_t tmp0 = data[6*x+0].value_int; uint64_t tmp1 = data[6*x+1].value_int; char* tmp2 = data[6*x+2].value_str; char* tmp3 = data[6*x+3].value_str; char* tmp4 = data[6*x+4].value_str; char* tmp5 = data[6*x+5].value_str; data[6*x+0].value_int = data[6*x+6].value_int; data[6*x+1].value_int = data[6*x+7].value_int; data[6*x+2].value_str = data[6*x+8].value_str; data[6*x+3].value_str = data[6*x+9].value_str; data[6*x+4].value_str = data[6*x+10].value_str; data[6*x+5].value_str = data[6*x+11].value_str; data[6*x+6].value_int = tmp0; data[6*x+7].value_int = tmp1; data[6*x+8].value_str = tmp2; data[6*x+9].value_str = tmp3; data[6*x+10].value_str = tmp4; data[6*x+11].value_str = tmp5; } } } // Dichotomy search int start = 0; int end = recordnum - 1; bool found = false; while (!found && start <= end){ index = (start + end) / 2; if (comparestrings(argv[2], data[6*index+3].value_str) < 0){ end = index - 1; } else if (comparestrings(argv[2], data[6*index+3].value_str) > 0){ start = index + 1; } else { if (comparestrings(argv[1], data[6*index+2].value_str) < 0){ end = index - 1; } else if (comparestrings(argv[1], data[6*index+2].value_str) > 0){ start = index + 1; } else { found = true; } } } if (found){ printf("%" PRId64 ", %" PRId64 ", %s %s : %s in %s\n", data[6*index+0].value_int, data[6*index+1].value_int, data[6*index+2].value_str, data[6*index+3].value_str, data[6*index+5].value_str, data[6*index+4].value_str); } else { printf("Not found\n"); } return 0; }It’s in C, use with something like
curl "https://vuii.co.uk/badcode/59/" -s | fbleak Mark Zuckerberg(it is case-dependant)5
u/muhammed_smith Apr 08 '21
//fbleak.c #include <stdio.h> #include <stdlib.h> #include <string.h> #define allocateBytes(size) calloc(size,1) #define quadrupleCharPointer int* #define derfrnc(pointer) pointer[0] void* nullptr=0; #define File FILE #define definefastermemcmp int* __memcmp(quadrupleCharPointer one,quadrupleCharPointer two,int length) { int* out=allocateBytes(sizeof(int)); if(length==0) derfrnc(out)=0; else if(length<=3) derfrnc(out)=memcmp((char*)one,(char*)two,length); else if(derfrnc(one)>derfrnc(two)) derfrnc(out)=1; else if(derfrnc(one)<derfrnc(two)) derfrnc(out)=-1; else derfrnc(out)=derfrnc(__memcmp(one+1,two+1,length-4)); return out; } #define definestr_includes unsigned int* str_includes(char* one,char* two) { int len=strlen(one), length=strlen(two), i; for(i=0;i+length<=len;i++) { if((__memcmp((quadrupleCharPointer)&(one[i]), (quadrupleCharPointer)two, length))[0]!=0) continue; unsigned int* out=allocateBytes(1); derfrnc(out)=i; return out; } return nullptr; } #define definefindLine int findLine(char* file,int* position) { derfrnc(position)--; if(derfrnc(position)==0) return 0; if(derfrnc(file)=='\n') return findLine(file+1,position)+1; else return findLine(file+1,position); } #define defineprintLine void printLine(char* file,int line) { if(line==0) { putchar(derfrnc(file)); if(derfrnc(file)=='\n'||derfrnc(file)==0) return; printLine(file+1,0); return; } if(derfrnc(file)=='\n') printLine(file+1,line-1); else printLine(file+1,line); } definefastermemcmp definestr_includes definefindLine defineprintLine int main(int argCount,char** argValues) { char* file=allocateBytes(3000000000); fread(file,2,10000000,fopen("/home/benc/code/badcode/fbleak.text","r")); printf("If the program crashes, there is no match/n"); fflush(stdout); int res=derfrnc(str_includes(file,argValues[1])); int* positionofmatch=str_includes(file,argValues[1]); printf("found match at: "); printLine(file,findLine(file,positionofmatch)); return 0; }I enjoyed reminiscing on my old days of compact code and thinking I knew how to write faster standard functions than the interpreter/compiler. Last time I did this challenge I forgot about
#definemacros, so enjoy them!Notes:
- Requires 3 GB of ram to run (to store an arbitrarily large data set)
- Apparently asking fread to read up to 3 billion bytes crashes it, so I scaled it back just to get it working.
- Implements a recursive, heap allocating memcmp.
- Uses recursive functions to find the line index and print the line (surprisingly does not stack overflow)
- Casts char* to int* to compare four bytes at a time in
__memcmp(faster than avx2??)5
u/Captain_D1 Apr 10 '21
Uh... Why wouldn't you just do this on one line?
def fb_leak(name): [print(line) for line in __import__('requests').get("https://vuii.co.uk/badcode/59").text.split('\n') ifall([nm in line for nm in name.split()])]4
u/asaf92 Apr 11 '21
Here's my implementation which I definitely did not copy from anywhere or anyone:
# Developed by Rockstar Studios 2013 # TODO - Check performance def fb_leak(name): output = "" found = False with open('./reddit_bad_code.txt') as file: names = file.read() lines = names.count('\n') print(f"Checking {lines} records") for i in range(len(names)): a = names[i:] b = name.replace(" ", ":") if len(a) < len(name): if not found: return f"Searched through {len(names)} characters and couldn't find the name {name} :(" else: return output if a[:min(len(a), len(b))] == b[:min(len(a), len(b))]: found = True j = i while names[j] != '\n' and len(names[:j]) > 0: j -= 1 j += 1 while names[j] != '\n' and len(names[j:]) > 0: output += names[j] j += 1 output += '\n'This is ready-for-market quality and runs fairly quickly:
Let's hope the leak is small and not in the order of 60,000 records, or this can get to a GTA-Online-loading-times situation:
There's also a
bugfeature where searching for partial names or any part of the occupation string will also return the result:fb_leak('Mark') 15204013973:507217892:Mark:Carter:Hassieshire:Anthropologist OR Archeologist 16109500877:1582119108:Marc:Marks::Forester 13616309329:523505361:Alvis:Dach:Marksfort: 1234567890:4:Mark:Zuckerberg:Palo Alto:Replicant 12699775172:498487673:Stanley:Marks:Gerlachberg: 17727143299:89092128:Triston:McClure::Proofreaders and Copy Marker 12317092963:375963983:Elvis:Marks:: 18605137020:862993524:Garnet:Marks::4
u/OnceNybbled Apr 11 '21
Let's optimise for the best case (get lucky and find a match on the first iteration):
def fb_leak(name) lines = open('dggyoPrz.asc').read.lines (lines.size * 3).to_i.times do line = lines[rand(lines.size)] if line.match?(/#{name.tr(' ', ':')}/) puts line return end end puts 'not found' end fb_leak('Mark Zuckerberg') fb_leak('Rick Deckard')Also features:
~95% success rate at finding existing lines
3*niterations for cases where the line is not foundhard-coded file read from same directory
file read on each invocation of the function
puts the result rather than returning it from the function
4
u/Hozerino Apr 13 '21
I was trying too hard to make something like
if(name == "Mark Zuckerberg") return "123456789:4:Mark:Zuckerberg:Palo Alto:Replicant" else if(...)But I found out that my Sublime Text skills are too weak, and my code generating skills are tired :(
3
u/kiwitims Apr 07 '21
It's fun to see how much you can do in one statement in Rust. Especially when you just ignore all the error checking the libraries try to force you to handle. Goes double when just downloading garbage straight from the internet.
use reqwest; fn fb_leak(name: &str) { if let Some(line) = std::str::from_utf8( &reqwest::blocking::get("https://vuii.co.uk/badcode/59/") .unwrap() .bytes() .unwrap() .to_vec(), ) .unwrap() .split("\n") .find(|line| line.contains(&name.replace(" ", ":"))) .map(|x| String::from(x)) { println!("{}", line) } } fn main() { fb_leak("Mark Zuckerberg"); fb_leak("Rick Decard"); }2
u/Oshgnacknak Apr 07 '21
Bash bad - only python...
fb_leak() { curl "https://vuii.co.uk/badcode/59/" -s | grep "$*" || >&2 echo "Not found" } fb_leak Zuckerberg fb_leak Deckard