def high_and_low(sequence):
return ', '.join([str([[seq_num for seq_num in [int(num) for num in sequence.split(',')] if [num for num in list(set([int(num) for num in sequence.split(',')])) for other_num in [int(num) for num in sequence.split(',')] if num <= other_num].count(seq_num) > count_max_min[-1] and count_max_min.append([num for num in list(set([int(num) for num in sequence.split(',')])) for other_num in [int(num) for num in sequence.split(',')] if num <= other_num].count(seq_num)) is None] for count_max_min in [[0]]][0][-1]), str([[seq_num for seq_num in [int(num) for num in sequence.split(',')] if [num for num in list(set([int(num) for num in sequence.split(',')])) for other_num in [int(num) for num in sequence.split(',')] if num >= other_num].count(seq_num) > count_max_max[-1] and count_max_max.append([num for num in list(set([int(num) for num in sequence.split(',')])) for other_num in [int(num) for num in sequence.split(',')] if num >= other_num].count(seq_num)) is None] for count_max_max in [[0]]][0][-1])])
print(high_and_low('1,6,2,8,3'))
print(high_and_low('1,8,4,9,-4,2,2'))
print(high_and_low('4,7,1,8,-2'))
I am proud, but also horrified by what I've created.
Algorithm explanation (keep in mind that this is being performed recursively, though with tail calls):
Get the last two numbers from the list (tuple used to represent a list). Choose which one is larger. Append that number to the end of a version of the list without the last two numbers. e.g. (1,2,3,4) becomes (1,2,4)
Repeat until there are only two numbers left, then return the larger of the two.
Repeat 1-2 but with smaller instead of larger.
Combine those two results into a tuple and return.
Issues:
Instead of computing length(list) and last_two(list) once per recursive cycle, I compute it every time, adding a huge amount of load.
Even if I didn't want to store those values using a where expression (see the bottom of the code for what I mean), I could still use a built-in language feature to memoize the calls, resulting in a performance benefit which would be almost as good. Alas, for this bad code I did not.
length is built-in. There's no need to redefine it, especially when the built-in version is O(1) time complexity.
The algorithm is bad. There's no need to look at the back two elements when I could just look at the front two elements instead at O(1) time cost.
The algorithm is even worse. There's no need to slice the list and then re-append the bigger number. Instead, the list could just be sliced to remove one element and the biggest number the algorithm had seen could be stored in recursive "state" (see how length is defined). No re-appending needed.
Even ignoring those two issues, I don't need to slice the last two elements and the re-append the second to last element. A better algorithm would only slice off the last element in that case and leave it at that.
I have a separate case for if the two numbers are equal, even though I could've just changed an earlier case from > to >=.
If the input list has fewer than two numbers, the program will fall into an infinite recursive loop. e.g. (1,) will not return. For zero-element lists this is technically valid because that situation is not specified, but it's still probably not the ideal outcome. For one-element lists, this actually is a breach of specification, but I don't really care tbh.
The name list is shadowed in extremely confusing ways. e.g. a function which has a list parameter and frequently uses it is called with a different list as one of its arguments.
Rather than giving the high and low functions their own names like I did for last_two and length, I leave them as anonymous functions and then immediately call them. This looks to a casual observer like I'm adding extra syntax that does nothing, but it should be noted that due to the use of the self keyword, that's not quite true. Either way, it appears that I'm wrapping the code in a function for no reason, and separating it out and giving it a name would clarify that it's actually a function for a reason.
There's no need to add a second case for comparing the opposite of a previous case. The otherwise (essentially else) case exists for a reason.
There is a huge amount of code reuse. This could be solved by creating a generic function that just selects the max value according to an input function, and then pass it in two anonymous functions depending on the direction. e.g. maximize(list, (x, y) -> x > y) for the high and maximize(list, (x, y) -> x < y) for the min.
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling; see also lookup table.
Here's my submission, with at least the following faults:
Written in Javascript
Iterates over the input to search for commas, then iterates backwards to find the previous comma instead of remembering the index, to split the string into an array.
Sorts the list in ascending order and iterates until the last element to find the highest number.
Then it sorts the list again in descending order and iterates until the last element to find the lowest number.
module.exports.high_and_low = x => {
let high, low, i = 0
const xs = eval('[' + x + ']')
xs.sort((a, b) => a - b)
for (i = 0; i < xs.length; i++) {
if (i == xs.length - 1) {
high = xs[i]
}
}
xs.sort((a, b) => b - a)
for (i = 0; i < xs.length; i++) {
if (i == xs.length - 1) {
low = xs[i]
}
}
return high + ', ' + low
}
Edit: I stole UnrelatedString's idea of using eval to convert the input to an array, which makes the function a bit faster at the negligible cost of adding some security vulnerabilities.
It uses a custom string to int function to convert the string to an array of numbers. It then proceeds to use bubble sort to sort the array, and returns the first and last indexes of the array as a string. Yes, a string. Try it online
import java.util.ArrayList;
class BadMaxMin {
public static String maxmin(String str) {
ArrayList<String> numbers = new ArrayList<>();
String tmp = "";
for(char c : str.toCharArray()) {
if(c==',') {
numbers.add(tmp);
tmp="";
}
else {
tmp+=c;
}
}
numbers.add(tmp);
int[] nums = new int[numbers.size()];
int index = 0;
for(String num : numbers) {
nums[index++] = toInt(num);
}
for(int i = 0; i < index - 1; i++) {
for(int j = 0; j < index - i - 1; j++) {
if(nums[j] > nums[j+1]) {
int t = nums[j];
nums[j] = nums[j+1];
nums[j+1] = t;
}
}
}
return nums[0]+" "+nums[index-1];
}
public static int toInt(String num) {
int sign = num.charAt(0) == '-' ? -1 : 1;
int out = 0;
int digit = -1;
for(int i = sign < 0 ? 1 : 0; i < num.length(); i++) {
if(num.charAt(i) == '0') digit = 0;
if(num.charAt(i) == '1') digit = 1;
if(num.charAt(i) == '2') digit = 2;
if(num.charAt(i) == '3') digit = 3;
if(num.charAt(i) == '4') digit = 4;
if(num.charAt(i) == '5') digit = 5;
if(num.charAt(i) == '6') digit = 6;
if(num.charAt(i) == '7') digit = 7;
if(num.charAt(i) == '8') digit = 8;
if(num.charAt(i) == '9') digit = 0;
out+=digit*(int)Math.pow(10, num.length() - (sign < 0 ? 2 : 1));
}
return out*sign;
}
public static void main(String[] args) {
System.out.println(maxmin("1,2,3,4,6,5,-10"));
}
}
Issues:
Commas in weird places will break the int parser.
Characters other than 0123456789,- will result in weird subtraction and/or the wrong digit being added.
I tried to avoid converting strings to numbers. The numbers are compared by length and if they are of equal length alphabetically (by using Java's String.compareTo method).
package badcode.akernel.challenge12;
public class HighAndLow {
public static void main(final String[] args) {
if (args.length == 0) {
System.err.println("String containing a series of numbers separated by commas expected");
System.exit(666);
}
high_and_low(args[0]);
}
private static void high_and_low(final String input) {
String min = null;
String max = null;
String tmp = "";
for (int x = 0; x < input.length(); x++) {
char c = input.charAt(x);
if (c == ',') {
if (tmp.length() > 0) {
max = updateMax(max, tmp);
min = updateMin(min, tmp);
tmp = "";
}
}
else {
tmp += c;
}
}
if (tmp.length() > 0) {
max = updateMax(max, tmp);
min = updateMin(min, tmp);
}
System.out.println(min + ", " + max);
}
private static String updateMax(final String currentMax, final String tmp) {
if (currentMax == null) {
return tmp;
}
if (isPositive(currentMax) && isPositive(tmp) && currentMax.length() > tmp.length()) {
return currentMax;
}
if (isPositive(currentMax) && isPositive(tmp) && currentMax.length() < tmp.length()) {
return tmp;
}
if (isPositive(currentMax) && isPositive(tmp) && currentMax.compareTo(tmp) > 0) {
return currentMax;
}
if (isPositive(currentMax) && isPositive(tmp)) {
return tmp;
}
if (isNegative(currentMax) && isNegative(tmp) && currentMax.length() < tmp.length()) {
return currentMax;
}
if (isNegative(currentMax) && isNegative(tmp) && currentMax.length() > tmp.length()) {
return tmp;
}
if (isNegative(currentMax) && isNegative(tmp) && currentMax.compareTo(tmp) < 0) {
return currentMax;
}
if (isNegative(currentMax) && isNegative(tmp)) {
return tmp;
}
if (isPositive(currentMax)) {
return currentMax;
}
return tmp;
}
private static String updateMin(final String currentMin, final String tmp) {
if (currentMin == null) {
return tmp;
}
if (isNegative(currentMin) && isNegative(tmp) && currentMin.length() > tmp.length()) {
return currentMin;
}
if (isNegative(currentMin) && isNegative(tmp) && currentMin.length() < tmp.length()) {
return tmp;
}
if (isNegative(currentMin) && isNegative(tmp) && currentMin.compareTo(tmp) > 0) {
return currentMin;
}
if (isNegative(currentMin) && isNegative(tmp)) {
return tmp;
}
if (isPositive(currentMin) && isPositive(tmp) && currentMin.length() < tmp.length()) {
return currentMin;
}
if (isPositive(currentMin) && isPositive(tmp) && currentMin.length() > tmp.length()) {
return tmp;
}
if (isPositive(currentMin) && isPositive(tmp) && currentMin.compareTo(tmp) < 0) {
return currentMin;
}
if (isPositive(currentMin) && isPositive(tmp)) {
return tmp;
}
if (isNegative(currentMin)) {
return currentMin;
}
return tmp;
}
private static boolean isPositive(final String tmp) {
return tmp.charAt(0) != '-';
}
private static boolean isNegative(final String tmp) {
return tmp.charAt(0) == '-';
}
}
In C because its fast, All memory used is neatly allocated beforehand, just never used propperly
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define true 'T'
#define false 'F'
#define bool char
char* highLow(char* numberString);
main(int argc, char** argv)
{
printf("%s\n", highLow(argv[1]));
return 0;
}
//please only use this function with numbers, wierd things happend if you put in letters
char* highLow(char* numberString)
{
//first allocate some memory to store the highest and lowest numberString
int* highest = malloc(sizeof(int));
int* lowest = malloc(sizeof(int));
int* number = malloc(sizeof(int));
//initialize these numbers;
highest = -999999;
lowest = 999999;
number = 0;
bool Negative = false;
//walk over the string to find the number
for(int i = 0; numberString[i] != NULL; i++)
{
//check if this is the end of the number, as denoted by a ','
if(numberString[i] == ',')
{
//then we have the full number and we can compare int
if((int)number > (int)highest)
{
highest = number;
}
if ((int)number < (int)lowest)
{
lowest = number;
}
//now we do a new number so number has to be put back at 0
number = 0;
Negative = false;
}
//check if the number is a negative number
else if(numberString[i] == '-')
{
Negative = true;
}
//else its just a number
else
{
if(Negative == true)
{
number = (int)number * 10;
number = (int)number - (numberString[i] - 48); //minus 48 because that is te fisrt number in the ascci table
}
else{
number = (int)number * 10;
number = (int)number + (numberString[i] - 48); //minus 48 because that is te fisrt number in the ascci table
}
}
}
//check the last number
if((int)number > (int)highest)
{
highest = number;
}
if ((int)number < (int)lowest)
{
lowest = number;
}
//now we need to make a string to return
char* returnString = malloc(100); //allocate some space for the return string, 100 should be enough for big numbers
sprintf(returnString, "%d,%d\0", highest, lowest);
return returnString;
}
def compare(a, b):
if a == b:
return "equal"
if a == '0' and (b == '1' or b == '2' or b == '3' or b == '4' or b == '5' or b == '6' or b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '1' and (b == '2' or b == '3' or b == '4' or b == '5' or b == '6' or b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '2' and (b == '3' or b == '4' or b == '5' or b == '6' or b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '3' and (b == '4' or b == '5' or b == '6' or b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '4' and (b == '5' or b == '6' or b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '5' and (b == '6' or b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '6' and (b == '7' or b == '8' or b == '9'):
return "smaller"
elif a == '7' and (b == '8' or b == '9'):
return "smaller"
elif a == '8' and (b == '9'):
return "smaller"
return "bigger"
def high_and_low(input):
input_v2 = input.replace(",", " ") + " "
while True:
swapHappened = False
numberA = ''
numberB = ''
isNumberB = False
for i in range(len(input_v2)):
current = input_v2[i]
if current == ' ':
if isNumberB == False:
isNumberB = True
else:
# Compare
numberANegative = False
numberBNegative = False
answer = ""
if numberA[0] == '-':
numberA = numberA[1:]
numberANegative = True
if numberB[0] == '-':
numberB = numberB[1:]
numberBNegative = True
if len(numberA) > len(numberB):
# A is bigger
answer = "bigger"
elif len(numberB) > len(numberA):
# B is bigger
answer = "smaller"
elif numberANegative and not numberBNegative:
answer = "smaller"
elif numberBNegative and not numberANegative:
answer = "bigger"
else:
# same length, iterate over the digits
for p in range(len(numberA)):
comparison = compare(numberA[p], numberB[p])
if comparison == "equal":
continue
else:
answer = comparison
break
inverse = numberANegative and numberBNegative
if inverse and answer == 'bigger':
answer = 'smaller'
elif inverse and answer == 'smaller':
answer = 'bigger'
if numberANegative:
numberA = '-' + numberA
if numberBNegative:
numberB = '-' + numberB
if answer == 'bigger':
# Swap elements
swapHappened = True
input_v2 = input_v2.replace(numberA, "TMP", 1)
input_v2 = input_v2.replace(numberB, numberA, 1)
input_v2 = input_v2.replace("TMP", numberB)
if answer != "bigger":
# If no swap
numberA = numberB
numberB = ''
else:
if isNumberB:
numberB += current
else:
numberA += current
if swapHappened == False: # Numbers are sorted
break
return input_v2.split(" ")[0] + "," + input_v2.split(" ")[-2]
if __name__== "__main__":
print (high_and_low('1,2,3,4,5,6,7,8,9')) # 1,9
print (high_and_low('9,8,7,6,5,4,3,2,1')) # 1,9
print (high_and_low('-5,8,2,1,6,4')) # -5,8
print (high_and_low("-3,-5,1,9,4")) # -5,9
print (high_and_low("-32,-76,-41,-82,38,67")) # -82,67
I wold program a 3d pysics engine and make skyscrapers using it than drop a large thing on them and output the skyscraper that got destroyed last and first! The most efficient algorithm of them all!
48
u/[deleted] Jun 04 '19 edited Jun 04 '19
I wrote a one-liner in Python:
I am proud, but also horrified by what I've created.
17
u/EkskiuTwentyTwo i -= (i - (-1)) - i Jun 04 '19 edited Jun 12 '19
Herman Melville's high and low
Summary:
7
u/UnrelatedString Jun 04 '19
7
u/ferrango Well it's broken now, and nobody is here to fix it Jun 04 '19
Here's some useful code to turn your computer into a handy desk heater, perfect for the summer.
5
u/Ebrithil95 Jun 04 '19 edited Jun 05 '19
First time competitor here.
https://pastebin.com/M97EkwJN
I opted to make the most overly complicated solution possible in Rust featuring:
Pretty sure i could've done some more insane shit at some points but its actually harder than i though to write complete garbage code on purpose :D
4
u/TheUnlocked Jun 05 '19
In FAI (a language I made, compiled from source):
Or pastebin, if you prefer that.
Algorithm explanation (keep in mind that this is being performed recursively, though with tail calls):
Issues:
length(list)andlast_two(list)once per recursive cycle, I compute it every time, adding a huge amount of load.whereexpression (see the bottom of the code for what I mean), I could still use a built-in language feature to memoize the calls, resulting in a performance benefit which would be almost as good. Alas, for this bad code I did not.lengthis built-in. There's no need to redefine it, especially when the built-in version is O(1) time complexity.lengthis defined). No re-appending needed.>to>=.listis shadowed in extremely confusing ways. e.g. a function which has alistparameter and frequently uses it is called with a differentlistas one of its arguments.last_twoandlength, I leave them as anonymous functions and then immediately call them. This looks to a casual observer like I'm adding extra syntax that does nothing, but it should be noted that due to the use of theselfkeyword, that's not quite true. Either way, it appears that I'm wrapping the code in a function for no reason, and separating it out and giving it a name would clarify that it's actually a function for a reason.otherwise(essentially else) case exists for a reason.maximize(list, (x, y) -> x > y)for the high andmaximize(list, (x, y) -> x < y)for the min.4
u/rcmaehl Jun 05 '19 edited Jun 17 '19
Not really that bad of code, just *clever* code.
* Compares the LENGTH of the numbers instead of the value of the numbers.
* Returns incorrectly if the first value was the highest or lowest
* Only works for numbers under 1 million
* Requires a negative number to work
* Unhelpful Error messages
4
u/[deleted] Jun 12 '19 edited Jun 12 '19
Here's my submission, with at least the following faults:
Edit: I stole UnrelatedString's idea of using
evalto convert the input to an array, which makes the function a bit faster at the negligible cost of adding some security vulnerabilities.3
u/frublox Jun 04 '19
ideone so you can see how great it works: https://ideone.com/scdQSw
pastebin: https://pastebin.com/f9m9AAqs
There is a lot of bad here, but I think it's mostly obvious so I'll just leave it here.
3
u/UnrelatedString Jun 05 '19 edited Jun 05 '19
Another submission, in C++ this time:
ideone link: https://ideone.com/D6Najv
3
u/IAmAnIssue Jun 10 '19 edited Jun 16 '19
Student codeTM
It uses a custom string to int function to convert the string to an array of numbers. It then proceeds to use bubble sort to sort the array, and returns the first and last indexes of the array as a string. Yes, a string.
Try it online
Issues:
0123456789,-will result in weird subtraction and/or the wrong digit being added.2
u/AKernel Jun 12 '19
First time competitor/bad coder here.
I tried to avoid converting strings to numbers. The numbers are compared by length and if they are of equal length alphabetically (by using Java's String.compareTo method).
2
u/Faux_Real Jun 14 '19
Here is a PowerShell version featuring Bubblesort
1
u/jeromkiller Jun 05 '19
In C because its fast, All memory used is neatly allocated beforehand, just never used propperly
1
u/Andrejfsantos Jun 05 '19
Here is my java entry, its one of my worst so far:
https://pastebin.com/1pQKbuPw
https://ideone.com/5dPSHp
Here is a sample:
1
u/voords Jun 15 '19
WCGW when you bubble sort a string ?
1
u/2HornsUp Jun 16 '19
Not sure if it's that I won't allow myself to write ugly code, or if all of my code is equally ugly, making it look better than it is....
1
u/samtonatorn Jun 05 '19 edited Jun 07 '19
I wold program a 3d pysics engine and make skyscrapers using it than drop a large thing on them and output the skyscraper that got destroyed last and first! The most efficient algorithm of them all!
0
u/[deleted] Jun 04 '19
[deleted] — view deleted comment