7
Your goal is to write a hash function, that accepts morse code character and returns a hash code that you get to define.
You can be sure, passed string will be:
- One of the Latin characters (A-Z) encoded into Morse Code using
.and-, or - One of the digits (0-9) encoded into Morse Code using
.and-, or - Empty
So, there could be any of 37 different strings passed to you.
Requirements:
- The returned number should be unique for all 37 strings
- For empty string the function should return 0
Score:
- Initially, you have a 100 points.
- You will lose
- 1 point for every bitwise operator in your code
- 2 points for every addition (subtraction) operator in your code (operators in loop clauses (e.g. inside
for(;;)orwhile()don't count) - 4 points for every multiplication (division, modulo, etc) operator
- 6 points for every if (else) statement
- 8 points for every loop statement (including loops in the called functions. You can presume that any called function has no more than one loop)
- 12 points for every conditional operator
- 200 points for using a built-in hash function
Bonuses:
- If all numbers, produced by your function are less than
N, you will get additional137 - Npoints (of course, if the bonus is positive)
Winners:
Score matters, but be creative!
Example:
Score: 100 - 5*2 - 3*4 - 8 + (137 - 134) = 73
I know, this could be improved by removing modulo operator and make a loop starts from 1, but this is just an example
#include <iostream>
#include <map>
#include <set>
std::size_t hash_morse(const std::string& s)
{
std::size_t ans = 0;
for(std::size_t i = 0; i < s.size(); ++i)
{
ans += (s.at(i) - '-' + 2) * (i + 1) * (i + 1);
}
return ans % 134;
}
int main()
{
std::map<std::string, char> m
{
{"", 0},
{".-", 'A'},
{"-...", 'B'},
{"-.-.", 'C'},
{"-..", 'D'},
{".", 'E'},
{"..-.", 'F'},
{"--.", 'G'},
{"....", 'H'},
{"..", 'I'},
{".---", 'J'},
{"-.-", 'K'},
{".-..", 'L'},
{"--", 'M'},
{"-.", 'N'},
{"---", 'O'},
{".--.", 'P'},
{"--.-", 'Q'},
{".-.", 'R'},
{"...", 'S'},
{"-", 'T'},
{"..-", 'U'},
{"...-", 'V'},
{".--", 'W'},
{"-..-", 'X'},
{"-.--", 'Y'},
{"--..", 'Z'},
{".----", '1'},
{"..---", '2'},
{"...--", '3'},
{"....-", '4'},
{".....", '5'},
{"-....", '6'},
{"--...", '7'},
{"---..", '8'},
{"----.", '9'},
{"-----", '0'}
};
std::map<std::size_t, std::string> hashes;
for(const auto& elem: m)
{
auto hash = hash_morse(elem.first);
if(hashes.find(hash) != hashes.end())
{
std::cout << "Collision" << std::endl;
std::cout << '"' << hashes[hash] << R"(" and ")" << elem.first << '"' << std::endl;
std::cout << "Hash: " << hash << std::endl;
std::cout << std::endl;
}
else
{
hashes[hash] = elem.first;
}
}
std::cout << "Total amount of collisions: " << (m.size() - hashes.size()) << std::endl;
return 0;
}
awesoon
Posted 2014-01-31T12:31:15.807
Reputation: 189
1What do you mean by "Score matters, but be creative"? I'm assuming the highest score wins, but you may want to clarify that. Is creativity solely a tie-breaker? If not, then it's not objective as is. – nyuszika7h – 2015-01-03T19:25:06.063
@soon Make sure you consider how well defined your scoring system is for more esoteric languages. Taking Brain-Flak as an example: Addition in Brain-Flak is implicit so it technically does not involve putting a addition operator in your code. At the same time it is done automatically so most of the results are not actually used. Also they way if clauses are made in Brain-Flak involves making a loop that never will run more than once. Would that count as a loop or an if/else and how should someone know for esoteric languages in general without asking?
– 0 ' – 2017-01-29T16:06:50.8201
Although this isn't an exact duplicate of Morse code to standard output, it's close enough that most answers will be portable both ways.
– Peter Taylor – 2014-01-31T12:46:57.947Wait, does string find/replace count as a loop? – Doorknob – 2014-01-31T13:24:32.890
By "binary operation" did you mean "bitwise operation"? Addition and multiplication are binary operations. – Kendall Frey – 2014-01-31T13:25:16.430
@DoorknobofSnow I think 'scanning' a string, and 'looping over' a string are semantically equivalent. – primo – 2014-01-31T13:30:27.073
@KendallFrey, yes, it was a typo. Thanks – awesoon – 2014-01-31T13:36:05.757
@DoorknobofSnow, yes. I've edited the post, thank you. – awesoon – 2014-01-31T13:44:51.610
What do you mean by "Hash code" is that like a hash function (that we get to define?), or is that some term in Morse? – McKay – 2014-01-31T13:57:02.567
"•If all numbers, produced by your function less than N" What? – McKay – 2014-01-31T13:58:39.043
"•Returned number should be unique for all strings" so that means that
longisn't a valid return type? because there are more than 2^64 different possible strings? – McKay – 2014-01-31T14:00:36.833We lose points for each operation that the program performs, or for each operator that we put into our code? – McKay – 2014-01-31T14:01:53.577
This phrase doesn't make sense: "(including loops in the called functions. Guess, that function has no more than one loop)" – McKay – 2014-01-31T14:02:34.080
@McKay, 1) yes, it's a hash function. 2) It means, that function should return numbers in range [0, N) for all correct strings. 3) Unique for all strings, that satisfies given requirements. 4) For each operator that we put into our code. 5) I mean, we don't know the number of loops in the called function. So, we guess, that called function has no more than one loop. – awesoon – 2014-01-31T14:09:37.177
2I'm pretty sure as soon as you remove loops, you remove turing completeness(recursion is still looping). – Cruncher – 2014-01-31T14:10:44.257
So, the objective is to define our own hash function? The phrase "return its hash code" implies that there already exists a hash code that we are to return, but no mention of what this hash code actually is. I presume that this implication is incorrect and that we get to define our own hash function? – McKay – 2014-01-31T14:11:53.020
@McKay, yes, the goal is to define a hash function. I'm going to rephrase it, thank you. – awesoon – 2014-01-31T14:15:10.217
I suggested a series of edits. That seemed easier than asking a hundred questions. – McKay – 2014-01-31T14:20:55.547
@soon You might want to clarify if all values produced by the hash should be unsigned (i.e. positive). You may also consider penalizing or disallowing direct hash look-ups.
– primo – 2014-01-31T15:55:55.023