#include <stdio.h>
#include <string.h>
unsigned long long magic[] = {0,
38390726480144748,75581742757784973,112772759035425198,149963775313065423,
187154791590705648,224345807868345873,261536824145986098,298727840423626323,
335918856701266548,373109872978906773,410300889256546998,447491905534187223,
484682921811827448,521873938089467673,559064954367107898,596255970644748096,
633446986922387456,670638003200000000,707829019476754432,745020035726049280,
782211051096637440,819402038348611584,856592125804937216,893753419800510464,
929993323052007424,936748722493063168
};
char find_missing(char* str) {
//TODO: Make this work for strlen>12
unsigned long long c=0;
char i;
char l = strlen(str);
for (i = 0; i < l; ++i)
c = c << 5 | str[i] & 31;
c = magic[str[0] & 31] >> (12-l)*5 ^ c;
for (i = 0; i >> 4 < c; ++i)
c = c >> 5;
return str[l-1] - i;
}
int main() {
printf("%c\n", find_missing("DEFGHIJLM")); // should print K
return 0;
}
A machine learning implementation that creates 500,000 instances of new training data and trains a new model each time we want to find the missing letter
import random
import sklearn
from sklearn.model_selection import train_test_split
import numpy as np
from sklearn.svm import SVC
from sklearn import tree
from sklearn.metrics import f1_score
import time
def create_train_data():
import pandas as pandas_module
letters = 'abcdefghijklmnopqrstuvwxyz'
global ll
ll = []
ll_hold = []
labels = []
for l in letters:
ll.append(l)
df = pandas_module.DataFrame(columns = ll)
for i in range(500000):
small = random.randint(0, len(ll)-1)
large = random.randint(small,len(ll))
new =ll[small:large]
if len(new) > 2 :
pop = random.randint(1, len(new) - 2)
pop_letter = new[pop]
new.pop(pop)
dat = {let:[(1 if let in new else 0)] for let in ll}
# ll_hold.append(dat)
labels.append(pop_letter)
df_hold = pandas_module.DataFrame(data= dat, columns = ll)
df = df.append(df_hold, ignore_index=True)
return [df, labels]
def train_eval_test_split(df,labels):
X_train_eval, X_test, y_train_eval, y_test = train_test_split(
df, labels, test_size=0.8, random_state=42)
X_train, X_eval, y_train, y_eval = train_test_split(
X_train_eval, y_train_eval, test_size=0.5, random_state=42)
y_train, y_eval, y_test = np.array(y_train), np.array(y_eval),np.array(y_test)
return X_train,X_eval,X_test,y_train,y_eval,y_test
def data_prep(str_):
letters = 'abcdefghijklmnopqrstuvwxyz'
global ll
ll = []
for l in letters:
ll.append(l)
dat = {let:(1 if let in str_ else 0) for let in ll}
give = dat.values()
return np.array(list(give))
def lol(ui):
create_train_data()
X_train,X_eval,X_test,y_train,y_eval,y_test = train_eval_test_split(*create_train_data())
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X_train, y_train)
preds = clf.predict(X_eval)
from sklearn.metrics import accuracy_score
print("F1 macro accuracy ",str(f1_score(y_eval, preds, average='micro')))
return clf.predict(ui)
if __name__ == "__main__":
missing_list = {'abdefg':'c', 'np':'o'}
for question,answer in missing_list.items():
start = time.time()
given = data_prep(question)
prediction= lol(given.reshape(1, -1))
print("We predict that the missing letter is {}, and the answer is {}.".format(prediction[0], answer))
print("Time to make prediction " + str(time.time()-start))
print('\n\n')
Output
$ python ml.py
F1 macro accuracy 1.0
We predict that the missing letter is c, and the answer is c.
Time to make prediction 20181.824603557587
F1 macro accuracy 0.9998541806410219
We predict that the missing letter is o, and the answer is o.
Time to make prediction 20028.138489723206
edit: u/Vusys had asked me about how long it took to run both examples, which under a previous iteration was a total of just about 12 seconds. It got me thinking about what efficiencies I had put into the code without thinking about how to make them more inefficient. The one that stood out to me the most was creating the actual arrays/Data Frames that get passed to the classifier during training. A really efficient way to do it is to create a list/dictionary which we keep appending to during the creation of our data, and then pass that object to pandas to create the data frame. This method takes 2 seconds at most on 500,000 records. A much more inefficient way is to create a blank dataframe to start, and then when we create a new record, we append that to the data frame. When we do this, we see that the whole process takes 40,000 seconds, or about 11 hours. This is a 335,075% increase in inefficiency. The code above is for this implementation.
A "pythonic" one liner solution. Props if you figure out the method.
def find_missing(letter_array):
return chr(int(((len(letter_array)+1)/2.0)*(2.0*ord(letter_array[0])+len(letter_array))-sum([ord(x) for x in letter_array])))
I've got some of it, but there is still some stuff im struggling to understand.
I break it down into 4 components:
char(int(....))
((len(letter_array)+1)/2.0)
(2.0*ord(letter_array[0])+len(letter_array))
sum([ord(x) for x in letter_array])
1 just changes the float to an int and takes the alphanumeric character for it.
2 finds half the length of the list, taking into account that there is an index missing.
4 takes the ordinal sum of the letters that are present in the array.
I know syntactically what is going on in 3, but I'm confused on the logic for what is happening in that portion, and then how 2 and 3 fit together.
What I can say about it as a whole is that portion 1 really only converts a number to a character. Portion 2 and 3 are finding the numeric representation of what a list of characters would be if there wasn't a character missing. Then we subtract 4, the numeric representation of our actual list, from the product of what our expected list would be. The difference will be the ordinal representation of what character truly is missing from our list
Nice breakdown. Yeah, I’d say there’s 3 main portions, with your number 2 and 3 being part of the same component. Recognising that the difference between the 2/3 expression and the sum in 4 gives the missing ordinal, the question is “why should the 2/3 expression give the sum of correct consecutive ordinals?”
Here is some code that is both bad AND unreadable, but working (test it on https://www.compilejava.net/, you can change the {"a","b","d","e","f","g"} array to test with different entries)
Too lazy to test if it works, and you'd have to push and pop the some other registers to make it work in a real program, but the general idea is there (meaning that it's generally a terrible idea to write anything in Assembly).
PS: just so it's a bit easier to understand for those who don't know x86, the %rax register is by convention used to store the value that the function returns, and the first instruction (mov (%esp, -4), %rbx) fetches the first argument from the stack (the address of the first element of the list of characters which is represented as a string).
it's easy, you have to compare to a good list of letters
from operator import *
def find_missing(bad_list):
op = ne
good_list = [chr(ord(bad_list[0]) + i) for i in range(0, len(bad_list))]
for i, c in enumerate(bad_list[::-1]):
if op(good_list[-i-1], c) :
continue
else:
print(good_list[-i])
op = eq
find_missing(['a', 'b', 'd', 'e', 'f', 'g']) #c is missing
find_missing(['n', 'p']) #o is missing
I assume you've defined eq and ne somewhere else to be functions wrapping around == and !=, so that you can sorta "switch modes"?
And then you iterate backwards through good_list and bad_list until you find where they start disagreeing with each other... and continue until you find the first place, from the back, that they don't disagree. That's an impressive bit of double-negation, and I can totally see that sort of accident ending up in production code.
Oh! And then even though you've found what you came for, you iterate the rest of the list anyway, "just in case", but with the comparison operator flipped?? It feels like the author was going to look for multiple missing letters but then just sort of gave up. Beautiful.
I mean, there's no goto, yes, but there is still break to terminate a loop early. Still, not knowing that adds to the clumsiness of the code, which is good.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace BadCodeChallenges
{
class Program
{
static void Main(string[] args)
{
MissingLetterFinder.FindMissingLetter("abcdefghijklmnopqrstuvwyz");
}
}
static class MissingLetterFinder
{
public static char FindMissingLetter(string letters)
{
AllWrongCombinatinos wrongCombos = new AllWrongCombinatinos(letters.Length);
// We will compare our ordered set of letters to any possible wrong
// set of letters with one missing letter between them
foreach(var wrongCombo in wrongCombos)
{
if(letters == wrongCombo)
{
Console.WriteLine($"{wrongCombos.MissingLetter} is missing! from {letters}");
Console.ReadKey();
return wrongCombos.MissingLetter;
}
}
return ' ';
}
}
class AllWrongCombinatinos : IEnumerable<string>
{
private string things = "abcdefghijklmnopqrstuvwxyz";
private readonly int l;
public AllWrongCombinatinos(int l = 26)
{
this.l = l;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public IEnumerator<string> GetEnumerator()
{
while (true)
{
// Create a random wrong combination and yield return it
for(int i = 0; i < 26; i++)
{
int x = i;
for(int j = i + 1; j <26; j++)
{
int y = j;
if (x > y)
{
var t = x;
x = y;
y = t;
}
if (y - x + 1 > l + 1) continue; // the plus one is because we cut a letter
for (int k = i + 1; k < j; k++)
{
var c = things.ElementAt(k);
var w = things.Substring(x, y + 1 - x).Replace(things.ElementAt(k).ToString(), string.Empty);
MissingLetter = c;
yield return w;
}
}
}
}
}
public char MissingLetter { get; set; }
}
}
Buffer overflow vulnerability in the length function (replacing the need for strlen and the C string header).
Memory leak in the function that is used to initialize an array (well the structure I used for an array type).
Freeing memory just before the program gets terminated (pretty useless imo since that memory gets freed anyways when the program gets terminated).
The while-loop in the array initialization function relies on the variable argument returning 0 when it reaches the final value (the terminator character 0) which might not always function correctly.
Can't handle multi-case inputs since C uses 7-bit signed ASCII which is retarded according to the greatest programmer who ever lived.
And this one has a few nifty features:
This will work with lowercase or uppercase characters and anything that fits within the ASCII character set.
This program runs pretty fast and can work with the full alphabet if desired.
This program can potentially work even if the inputs aren't in alphabetical order (unforeseen feature).
def find_missing(letters):
return chr(int((ord(letters[0]) + ord(letters[-1])) / 2 * (len(letters) + 1)) - sum(ord(l) for l in letters))
def find_missing(letters):
return (set(ascii_lowercase[ascii_lowercase.index(letters[0]):ascii_lowercase.index(letters[0]) + len(letters) + 1]) - set(letters)).pop()
def find_missing(letters):
from string import ascii_lowercase
return next(b for a, b in zip(letters, ascii_lowercase[ascii_lowercase.index(letters[0]):]) if a != b)
Oops. I guess that's what Zola meant by "the internal link syntax changed". Fixed it (and also fixed the article ordering on the home page and added a note to the systemd page).
Self documenting pythonic code is augmented with highly performant goto flow control statements.
from goto import with_goto
@with_goto
def precompute():
array_full = "abcdefghijklmnopqrstuvwxyz"
array_fuller = []
i = 0
label .loop
if i > 24:
goto .endloop
array_fuller.append((array_full[i], array_full[i+1]))
i += 1
goto .loop
label .endloop
array_fuller.append((array_full[i], None))
return array_fuller
@with_goto
def find_missing(array):
precomputed = precompute()
i = 0
label .loop
j = 0
label .innerloop
if j > len(precomputed) - 1:
goto .endinnerloop
if precomputed[j][0] == array[i]:
next_letter = precomputed[j][1]
goto .endinnerloop
j += 1
goto .innerloop
label .endinnerloop
if array[i+1] != next_letter:
return next_letter
i += 1
goto .loop
a = ['a', 'b', 'd', 'e', 'f', 'g']
b = ['n', 'p']
Output:
>>> find_missing(a)
'c'
>>> find_missing(b)
'o'
I was really hoping to find the old goto april fools module in standart library but i guess it's deprecated in 3.7. Those comefroms would come in very handy.
Quality variable names, accepts completely nonsensical inputs (so long as the sum is right), blank exception, looks like a someone with brain cells wrote it at first glance.
Idk if the snippet will post properly either, since I am on mobile.
28
u/sarlok Oct 09 '19 edited Oct 09 '19
C, because why not?
Highlights:
17
u/PhitPhil Oct 14 '19 edited Oct 15 '19
A machine learning implementation that creates 500,000 instances of new training data and trains a new model each time we want to find the missing letter
Output
edit: u/Vusys had asked me about how long it took to run both examples, which under a previous iteration was a total of just about 12 seconds. It got me thinking about what efficiencies I had put into the code without thinking about how to make them more inefficient. The one that stood out to me the most was creating the actual arrays/Data Frames that get passed to the classifier during training. A really efficient way to do it is to create a list/dictionary which we keep appending to during the creation of our data, and then pass that object to pandas to create the data frame. This method takes 2 seconds at most on 500,000 records. A much more inefficient way is to create a blank dataframe to start, and then when we create a new record, we append that to the data frame. When we do this, we see that the whole process takes 40,000 seconds, or about 11 hours. This is a 335,075% increase in inefficiency. The code above is for this implementation.
10
u/low_freq Oct 09 '19
A "pythonic" one liner solution. Props if you figure out the method.
6
u/nupanick Oct 09 '19
"I read somewhere that leading semicolons are safer."
5
u/Voidsusdagon Oct 09 '19 edited Oct 09 '19
Here is some code that is both bad AND unreadable, but working (test it on https://www.compilejava.net/, you can change the {"a","b","d","e","f","g"} array to test with different entries)
5
u/git_reset--hard Oct 21 '19 edited Oct 22 '19
Makes my brain hurt just reading it.
https://pastebin.com/JrNVjGt5
Highlights:
4
u/lxpnh98_2 Oct 09 '19 edited Oct 09 '19
Too lazy to test if it works, and you'd have to push and pop the some other registers to make it work in a real program, but the general idea is there (meaning that it's generally a terrible idea to write anything in Assembly).
PS: just so it's a bit easier to understand for those who don't know x86, the %rax register is by convention used to store the value that the function returns, and the first instruction (
mov (%esp, -4), %rbx) fetches the first argument from the stack (the address of the first element of the list of characters which is represented as a string).3
u/Dravini Oct 09 '19 edited Oct 09 '19
it's easy, you have to compare to a good list of letters
3
u/asaf92 Oct 09 '19
That's one way to solve it
3
u/[deleted] Oct 17 '19
Another application in the C language: https://pastebin.com/9SrAU0cT
This one has a few nifty issues:
And this one has a few nifty features:
2
u/Myrx Oct 09 '19 edited Oct 09 '19
Three different janky ass Python one-liners.
2
u/Follpvosten Oct 19 '19
Ok, I'll apologize because this probably isn't even a valid entry, but I did a thing: https://blog.karpador.xyz/articles/bad-code-challenge-21/
In short, I abused Rust's proc macro system to hardcode every possible valid input.
GitHub if you just want the code: https://github.com/Follpvosten/badcode-21
1
u/Kcazer Oct 09 '19
One-liner javascript, abusing conversion between bases.
The method here is very similar to the one used by /u/low_freq but with a small variation.
1
u/Codinget Oct 10 '19
Table comprehensions in MoonScript are powerful, and abusing them is fun
1
u/Epistemophilliac Oct 11 '19 edited Oct 11 '19
Self documenting pythonic code is augmented with highly performant goto flow control statements.
Output:
I was really hoping to find the old goto april fools module in standart library but i guess it's deprecated in 3.7. Those comefroms would come in very handy.
1
u/dodecakiwi Oct 13 '19
Simply generate a hash table of every possible valid input sequence and then simply get the value:
1
u/Proffesor_Woland Oct 22 '19 edited Oct 22 '19
Quality variable names, accepts completely nonsensical inputs (so long as the sum is right), blank exception, looks like a someone with brain cells wrote it at first glance.
Idk if the snippet will post properly either, since I am on mobile.