Programming 1

[OnlyHuman]

I solved this a long time ago, but since we seem to be disclosing different methods for how this can be done, I thought I'd share mine so that it might help some other people. I used a priority queue the first time, based on a predicate that a given string will have a total product x given by:

x = ∏ ci : where ci is the ASCII value of the character in the input string at position i.

The predicate automatically put the correct unscrambled word at the top of the queue. It was fast, but I've since redesigned it to remove the redundancy. Now I use a hash table where the total string product of an unscrambled word is a key to that same word as a value. For example:

__key__ __value__
1256742 => foo

Now any scrambled word can be found in the unscrambled list by indexing into the table using the current scrambled word's total string product. It's extremely fast that way.

[Neurotrace]

So I've got my descrambler written in C++ but I'm having issues with time. I could cure this if I could find a way to check a char array for the first character that isn't a space or # then basically slide the entire char from that point on to the first position and then reassign the size of the char array so I don't have a bunch of trailing empty slots. Any suggestions?

[msbachman]

So I've got my descrambler written in C++ but I'm having issues with time. I could cure this if I could find a way to check a char array for the first character that isn't a space or # then basically slide the entire char from that point on to the first position and then reassign the size of the char array so I don't have a bunch of trailing empty slots. Any suggestions?

This isn't the most suave advice but how I did it was to manually edit out the "# " that preceeded each word when I copy-pasted it into a file. Then I ran my program and it spit out the answer, I grabbed it, and pasted it back in.

The key combo you'd probably have to use for windows would be something like "home, (up arrow to top of file), delete,delete,delete,down arrow,home,delete,delete...," etc. It's probably about the same to how i did it with vim.

I'll post back some code that would let you do what you asked, it won't be directly applicable to the challenge but it might help you.

-- Wed Jun 30, 2010 10:47 pm --

Code: Select all

#include <stdio.h>
#include <string.h>

int h_val(char * str)
{

int i=0;
int h_total=0;

while(*str != '\0')
{
if(*str == ' ' || *str == '#')
;
else
h_total+=*str;

++str;
}

return h_total;
}



int main()
{
char test[]="#  abc";


int res= h_val(test);

printf("%i\n", res);

}


Hope that helps a bit. There might be problems with it mind you, I only tested it a few times. It just skips over the troublesome characters.

[Neurotrace]

Oh ok. I get that. The only problem I see with that is that after a char[] has been initialized, you can't really change the size, right? Because I'm using that same array for all 6 or 8 or however many scrambled words there are and I don't think they're all the same length.
I do appreciate the "skip the characters" code though. Very helpful

[msbachman]

Oh ok. I get that. The only problem I see with that is that after a char[] has been initialized, you can't really change the size, right? Because I'm using that same array for all 6 or 8 or however many scrambled words there are and I don't think they're all the same length.
I do appreciate the "skip the characters" code though. Very helpful

Cool! Glad it helped. I'm no C expert but I don't believe you can resize arrays dynamically like that; at least it wouldn't be easy to do it.

What you CAN do is null terminate it and use things like strlen that look at the size of the array by where the '\0' is placed. You could also make a function that takes the array and returns a pointer to a different sized char array. Really though I'd use the former method, because all a char array really is is a set of bytes and you use it (typically) until you hit the null terminator.

How I did it was the former. I just made one char array of some arbitrary size (adequately big), say 40 bytes, and then made sure that each time I wanted to use it the null terminator was in the right place.

I'd offer to swap code maybe to see more specifically what the problem is in PMs but frankly I don't know anything at all about C++ except aspects that are directly taken from C.

[Neurotrace]

Oh wow, that's awesome timing. I just got through setting it up to determine the length by finding the '\0' lol I found a way to basically create a char[] dynamically. Tell me what you think:

Code: Select all

int startCheck = 0;
cin.getline(stringy, 20);
l = strlen(stringy);
for (int i  = 0; i < l; i++)
     if(stringy.charat(i) != 32 && stringy.charat(i) != 34 && startCheck ==0) {
          startCheck = i;
          l = l - i;
      }
char word[l];


It's not verbatim but it's enough to get the idea across.

[msbachman]

I'm notoriously bad at reviewing others' code...especially in C++, it looks familiar but for some reason my mind doesn't process it the same...lack of experience in C++ I guess.

So there's a for loop, then the if statement checks to see if it's a space or a double-quote mark (? why this and not '#'? those are what get pasted in when I copy the stuff from the website), as well as if startCheck ==0. I'm not sure but you might want a 35 instead of a 34 in the code.

Wouldn't the startCheck not be incremented? I'd think you'd want it to be incremented to count the number of characters to reduce the length by.

Like you said, if it's not verbatim, it probably works great. Glad to see you figiire it out.

[Neurotrace]

Oh, oops. I was writing this and trying to talk on the phone at the same time. Multitasking is not my strong point. Let me paste that back fixed

Code: Select all

int startCheck = 0; // This variable will be what determines where in the array is the letter
cin.getline(stringy, 20); // Just take in a given string, in this case a scrambled one
l = strlen(stringy); // Copies the length of the string. I use this to compare scrambled word length against wordlist
for (int i  = 0; i < l; i++) // Standard for loop :P
     if(stringy.charat(i) != 32 && stringy.charat(i) != 35 && startCheck == 0) { // if character at position i in the string is not a space or # and if the startCheck is equal to 0 then
          startCheck = i; // Assign startCheck to first real character
          l = l - i; // Take the extra length off
      }
char word[l]; // Create array with that length


Then a bunch of shenanigans before and after but you get the point. Hopefully I'll get a chance to write it and try it out tonight. I'll post results ;D

[wizerdb]

I am trying to write my script for this mission in python. Right now I am trying to test out a piece of code to see if it works before I write out the whole thing just to find it doesn't.
This is what I have atm

Code: Select all

import fileinput

scrambled = 'scrambled.txt'

for line in fileinput.input(scrambled):
    for x in line:
        wrd = ""
        if x != " ":
            wrd = wrd+x
    print wrd
    raw_input("Press ENTER to continue...")

raw_input("Press ENTER to exit...")

It is supposed to print each word, excluding new line, pause, then when you hit enter move on to the next word. HOWEVER, instead of printing the word (the scrambled word btw), it prints a blank line, except for the last word in which case it prints "n" which is the last letter of the last word (it does not have a new line after it). Could someone tell me what I am doing wrong please?

Thanks in advance!!

[edit] I am using this code instead of simply "print line" because I will need some of this so that I can have it print the unscrambled words later WITHOUT the new line, just word1,word2,etc [/edit]

-- Tue Jul 20, 2010 1:55 pm --

Nvm about my last message, I found a new way to right it using indices that works.
If there is someone out there also using python for this and is having trouble like I was, here is the new script (btw, this was only to test a piece of code I'd need for the final)

Code: Select all

import fileinput

scrambled = 'scrambled.txt'

for line in fileinput.input(scrambled):
    show = line[0:-1]
    print show
    print len(show)
    print
    raw_input("Press ENTER to continue...")
    print

raw_input("Press ENTER to exit...")


[rsrvctrl]

Just finished this mission using plain old batch (windows command line scripting). About 50 lines of "code". I used the following method:

1. split the wordlist.txt by char count
2. loop through the scrambled words one-by-one
3. for a given scrambled word, select from the wordlist only words with matching char count
4. for a given scrambled word, check for multiple occurrences of the same char, and select from previous selection words only containing multiple occurrences of the same char
5. for a given scrambled word, loop through the word char by char, each time selecting from previous selection only words containing the specific char (narrowing the subset each pass)

The above method made my batch script solve this mission in about 5 secs, which is a VERY long time compared to more powerful scripting -or even programming languages.

(Admittedly, on my workstation, I could solve it, but not in time. Needed a relatively powerful server to make it in 5 secs. If you also want to try batch, use loads of variables, and avoid temp files to store/load temporary data. Piping the result to 'clip' also saves time.)