Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
Magnetic North
Dec 15, 2008

Beware the Forest's Mushrooms
Sometimes, a video game or a service or something will give you a very short password, often in a short hex or decimal number that can preserve the game state in some way. For instance, Megaman X (as seen on this random website https://www.mmhp.net/Passwords/MMX1/) has its passcodes written as a 12 digit number. For this game, there are 24 boolean states (is Armored Armadillo defeated, did you get Leg Upgrade, etc). So there are 224 possibilities or 16.7 million possible states. Since that is much smaller than a 12 digit number, you can imagine being able to encode these values to individual numbers. All zeros for nothing, all zeros except one 1 for Armored Armadillo being defeated, etc. Obviously no one is manually writing all 16 million states, so it has to somehow be somehow mathematically encoded. Under the hood it can just be 24 bits arranged into a number, but it doesn't appear to actually be quite that simple. I'm sure there's some binary compliment that can obfuscate these things, but I am dumb.

MMX is just an example. I am broadly curious about taking these complex states and encoding them into something short and record-able by a human without being human-readable. I have no idea how to even ask Google about this topic since I don't know what to call it, and looking up about passwords and encoding just gives me cybersecurity stuff.

Adbot
ADBOT LOVES YOU

nielsm
Jun 1, 2009



Well you already said the word, encoding. I don't think there is any term for this specific case, it's just about choosing an appropriate alphabet for the coding and an algorithm for the transformation. It's largely about making tradeoffs in various parts: How much data needs to be recorded, how resilient must it be to attacks (e.g. players entering random codes), how long do you want the coded values to be, what kind of input method can you offer to enter the codes into the game, etc.

In your given example, you have 24 bits of data, and you want to encode it into 12 decimal digits.
24 bits is easily split up into 3 bytes of 8 bits, and the 12 digits can also be split into 3 groups of 4 digits. That would be two bits per digit, but one decimal digit can encode three bits (values 1, 2, 4, aka. octal), so it'd only be stuffing 8 bits into a space that can hold 12 bits. Well, what about adding a checksum then, generate a 12 bit checksum of the 24 bit data, and distribute the checksum bits out among the actual data-coding bits. Now you have a 36 bit space of possible values, and depending on the specific checksum algorithm, possibly only 1/4096 randomly guessed codes would actually be valid.

The Fool
Oct 16, 2003


Here's a really good writeup on how the original metroid did it: https://gamefaqs.gamespot.com/nes/519689-metroid/faqs/39232

Computer viking
May 30, 2011
Now with less breakage.

A less specific example that sees a lot of use is Base64.

In short, and stealing liberally from wikipedia:
- Despite the name, the output uses 65 characters, all of them normal printable characters you can type on a US keyboard. These were picked because they're "safe" - they will go through even the wonkiest old email servers, encodings and transfer methods with no issue.
- 64 choices is enough for 6 bits - 2^6 is 64. So each character you add is worth 6 bits of information.
- The 65th character is special, we'll get back to it. It's always (?) the equals sign.

With that in mind, you just create a table assigning a binary number to each character. For Base64, a common version starts at A=000000 and ends at /=111111 - there's a table in the wikipedia article. Then you grab 6 and 6 bits from your input, and output the appropriate character. This lines up every 24 bits (three input bytes = four 6-bit output characters), but if your input length isn't a multiple of three you can run out of input with two or four bits left over. The solution in base64 is to pad the input with zeroes, and then use the 65th character to indicate how much padding you had to add: One equals sign means "we had to add two zeroes", and two means "four zeroes".

As an example:
Say we have just two bytes of state: One for "things we've unlocked" and one for "amount of gold". Not super realistic, but easy to extend.
code:
-+-+-+---
 |1|1| Starter gun
B|2|1| Unlocked first door
y|3|1| Killed tutorial boss
t|4|1| Missile launcher 
e|5|0| Minimap unlocked
 |6|0| Beam gun
1|7|0| Wall climbing
 |8|0| Missile charge shot
-+-+-+---
 |1|0|
B|2|0|
y|3|1| Gold: 
t|4|1| 00110010 = 50
e|5|0|
 |6|0|
2|7|1|
 |8|0|
-+-+-+--
Stack the bits after each other and split into groups of 6. Then look up each of the 6-bit codes in the table from the wikipedia article.
We run out of bits at the end, so we need to add two padding zeroes at the end:
code:
Bits: 111100 000011 0010..  2 bits padding
      123456 123456 123456
out:       8	  D      I     =
Which means we just converted our 16 bits of input into the Base64 string 8DI=

There's a lot you can do with that basic idea, both before encoding (encryption, checksums) and after. A fun variant for short codes is to have a dictionary of English words instead of single character outputs: If you find 256 unique words, each input byte is one unique word; if you can find 1024 inoffensive words they're worth 10 bits each.

e: And yes that metroid writeup is indeed good.

PhantomOfTheCopier
Aug 13, 2008

Pikabooze!
The search terms you seek are canonical representation or form, which is often used as a state space representation.

At a very high level it could be as straightforward as "the lexicographic key ordered json output of all (basic) variables". For games this is almost always position, orientation, speed, and other physical parameters. Objects, scoring, historicals, may also matter. Sometimes this is inherently lossy. For example, it may be sufficient to start in the correct "area" even if the position is not equivalent.

A more efficient canonical form generally maps the bits of information, as nielsm showed above, but this requires a binary channel of communication. Encoding is when you take your binary state and perform a conversion to avoid protocol issues, eg Base64. Generally canonical forms will provide a binary conversion, because it's easy to analyze mathematically, but you can also have direct conversion to other encodings as needed.

Developers love to get clever here, so you may see short lowercase alphas (26^6=308M versus 64^6=68B), or just alphas (52^6=19B) which users will likely get wrong with manual re-entry. (The worst is when teams decide they need full UUIDs, which are never "human readable", even though they only need a few bytes of entropy and don't have distributed concurrency concerns anyway). If entry is entirely manual there are options like word-based encoding (horse stapler) as sometimes used in s/key implementations, or now in what3words. Users can likely handle some numbers, however, so "Eddy tide comb 7663" can be adequate, but you'll still be limited to smaller spaces.

Also consider what needs to be plain/visible, obfuscated, or encrypted. IE if data is already known to the user and doesn't impact application behavior, it doesn't need to as guarded (eg username). cf check algorithm (crc).

Magnetic North
Dec 15, 2008

Beware the Forest's Mushrooms
Thank you all. That is all very informative. I fear some of it is over my head, but baby steps I guess.

Volmarias
Dec 31, 2002

EMAIL... THE INTERNET... SEARCH ENGINES...

Magnetic North posted:

Thank you all. That is all very informative. I fear some of it is over my head, but baby steps I guess.

Figure out what you want to do before you get fancy about it. For your first version, just have the user enter straight hex values that map directly to values, like you mentioned originally. Change that up later on and use that different encoding once you've figured out what you want to actually keep track of.

Some games just use obfuscated JSON as save state. Don't overthink it.

goodness
Jan 3, 2012

When the light turns green, you go. When the light turns red, you stop. But what do you do when the light turns blue with orange and lavender spots?
I think the answer is no, but are there any CS related positions in remote areas (not remote work from home but like far from civilization/harsh areas) that pay exceptionally well because of their remoteness? US, EU, SEA. I figure anything like that would just employ someone from home for cheaper instead of paying to bring them out that far like they have to for other positions requiring in-person work.

Dijkstracula
Mar 18, 2003

You can't spell 'vector field' without me, Professor!

Also the glut of newly minted phds every year means there’s always someone willing to up and move to Hoople, ND to teach seven sections of intro C++ for peanuts

There are schools that are not necessary in the most obvious places that are known to pay better than average (ETH and Singapore come to mind and I’m sure there are others) but the “remoteness” isn’t really a factor there

E: my answer was more geared towards academic CS positions as I thought I was in the grad school thread :shobon: )

Dijkstracula fucked around with this message at 20:52 on Jan 15, 2024

ultrafilter
Aug 23, 2007

It's okay if you have any questions.


Those positions might exist in small numbers on military bases in the rear end end of nowhere for people with Top Secret clearances and very specific skill sets.

leper khan
Dec 28, 2010
Honest to god thinks Half Life 2 is a bad game. But at least he likes Monster Hunter.

ultrafilter posted:

Those positions might exist in small numbers on military bases in the rear end end of nowhere for people with Top Secret clearances and very specific skill sets.

they wanted exceptional pay, not just remoteness

goodness
Jan 3, 2012

When the light turns green, you go. When the light turns red, you stop. But what do you do when the light turns blue with orange and lavender spots?
Yeah, just starting to look for something new and also looking to move at the same time (somewhere with more extreme weather than NC, its way too mild for me here). Don't see myself getting a clearance anytime soon since I actively use cannabis and have tried quite the selection of other things in the last decade.

Hopefully can stay fully remote but really I'd move anywhere in the US for a couple years if I can double up my pay.

goodness fucked around with this message at 00:23 on Jan 17, 2024

Volmarias
Dec 31, 2002

EMAIL... THE INTERNET... SEARCH ENGINES...

goodness posted:

Yeah, just starting to look for something new and also looking to move at the same time. Don't see myself getting a clearance anytime soon since I actively use cannabis and have tried quite the selection of other things in the last decade.

Hopefully can stay fully remote but really I'd move anywhere in the US for a couple years if I can double up my pay.

Best case scenario for "pay me a lot to be absolutely nowhere" is to find an unexpected boom town, then show up to take all the money miners / drillers / whoever throw around. Somehow. Maybe talk about NFTs or something.

acidx
Sep 24, 2019

right clicking is stealing
Newbie here looking for some advice on building a small application for work. The end state we're moving towards is having one SQL instance where we collect and house all of our production data. I taught myself a little bit of SQL over the last year, and developed a working model of the back end in SSMS. Now I'm trying to learn how to make an application to serve as the front end.

Our requirements are for different users on our network to be able to access different pages in the app based on their windows credentials. Most of the pages in the application would be basic CRUD stuff. Maybe 10 of these pages total. These would be for internal use, so they need to be clean and function well, but they don't need to be super pretty. The other category of page would be display pages that are able to go full screen, for use on wall monitors. Probably a couple of these to display real time SQL data in graphs and such. Optional but awesome would be a display page that is designed for mobile browsing.

Based on my early research, I think the best option for doing all of this is a web app. I have 0 experience with javascript, python, html, or anything with a C or an F. I'm pretty good with VBA and SQL, but it doesn't seem like that is going to be super useful for this project. I did a little reading, and the things I keep seeing are asp .net core and blazor. It seems like there's lots of resources showing how to do exactly what I'm trying to achieve in visual studio, which I'm going to need in order to limp through the C#, so those are what I have been gravitating towards. But I haven't done a deep dive into it all yet. It could be there's a better option for me that I don't know, or that that I'm overlooking something obvious.

So in short, I'm very new and I don't know what I don't know. Any tips?

nielsm
Jun 1, 2009



You're on the right path, for now.

The frameworks you'll be working with try to enforce various patterns, splitting things into layers and separation of concerns. It will be overwhelming at first, and you will probably feel an urge to "just do something simpler". Fight that urge. It will be far more painful to try going against the prescribed patterns in the long run.

Before you try to do something, make sure you can do nothing. Start with minimal pieces and "hello world" style of things. Build experimental, small, stand-alone programs that only do a single, very simple thing. Then when you know you can do that thing, you can start integrating it in the real software. Eventually, you might want to do those things by writing classes/modules and unit tests for those.


Edit: And learn to love the command line. It's often much simpler to write small command-line tools or programs to test things, than it would be to wrangle a GUI for the same thing. PowerShell can also be a really good friend, in how it's able to load .NET assemblies and call the code directly.

nielsm fucked around with this message at 08:42 on Jan 18, 2024

dirby
Sep 21, 2004


Helping goons with math
I wish I had a better way to access things for this, but I probably can't:
On a website behind a login, there's a page with a gigantic table (let's say 50k rows after it all loads), I would like to automate the checking of checkboxes in certain rows. But I know the exact format of the HTML I'm looking for: e.g. the first td tag will have a checkbox made with an input tag and the rows I care about will have the seventh td with class "foo" and the data will be of the form "<a href ...>17</a>".

Is there an easy way to script this, maybe with a browser extension or something?

My criterion is so simple that any language should be fine.

nielsm
Jun 1, 2009



That's a perfect use case for a Greasemonkey (or similar) user script.

mystes
May 31, 2006

If it's one off: just do it in the chrome developer tools

If you need to do it a couple times: you can just make a snippet in the chrome developer tools and run that

If you need to do it a lot interactively: you can take the snippet and make it into a greasemonkey script or something once it's working

If you need to do it automatically with no interaction then it's more complicated, but I'm guessing that isn't the case if you just want to check checkboxes


You could theoretically try to do some really complicated css selector or xpath to get the exact input elements but it's probably simpler to get the rows or the elements that contain the data you want using document.querySelectorAll and then iterate over them and check the boxes within the rows/parent elements

mystes fucked around with this message at 22:50 on Jan 19, 2024

dirby
Sep 21, 2004


Helping goons with math

mystes posted:

...
If you need to do it a couple times: you can just make a snippet in the chrome developer tools and run that
If you need to do it a lot interactively: you can take the snippet and make it into a greasemonkey script or something once it's working
...
but it's probably simpler to get the rows or the elements that contain the data you want using document.querySelectorAll and then iterate over them and check the boxes within the rows/parent elements
Thanks! I think this should suit my needs.

ninjoatse.cx
Apr 9, 2005

Fun Shoe
What’s framework do people recommend for multi platform development (ios, android, desktop). I was looking at flutter, but it doesn’t seem really popular around here. I also looked at ionic, but I’m not sure how “universal” its features are.

pokeyman
Nov 26, 2006

That elephant ate my entire platoon.
Flutter.

(I haven't used it, only done native apps, but it's what I would try first.)

Surprise T Rex
Apr 9, 2008

Dinosaur Gum
I use Flutter at day job and it’s surprisingly nice. There’s a few things Dart has no good support for (case-insensitive JSON deserialisation ala Newtonsoft, it has a terrible datetime built in) but I genuinely rate it.

My only other cross platform dev experience is Xamarin however so maybe it’s only nice compared to that?

Ihmemies
Oct 6, 2012

I am quite stuck. I have a collection of 20 000 numbers, they can be anything from 1 to 1000 000 000. I also have a bunch of other numbers and for each of them I need to find and "remove" the closest matching number from the list.

I can use binary search to find such numbers, but I really have no idea how to avoid using the same number twice and be fast enough. If the numbers were unique, I could just use a set. If I use a vector, vector.remove(index) is painfully slow.

Like where to even begin? What kind of data structure would even work, so I could efficiently search for closest matches and remove them or mark them as used..

moctopus
Nov 28, 2005

Can you swap the found number with the last number in your collection then do a binary search on a collection of one less size? Repeating for each found number?

Edit: I guess that may mess with the ordering too much.

Maybe create a binary tree?

moctopus fucked around with this message at 11:36 on Jan 31, 2024

Computer viking
May 30, 2011
Now with less breakage.

A tree of some sort could work, yeah. A binary tree has decent average search and delete times and is easy enough to implement, so that's a good start. I think a B-tree would perform better here, but if you have to write it yourself it may not be worth it.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
Your two reasonable options would be a (potentially balanced) binary search tree, or just leaving tombstones whenever you use an entry and doing a linear scan outwards to find the next nearest unused value.

Xerophyte
Mar 17, 2008

This space intentionally left blank

Ihmemies posted:

I am quite stuck. I have a collection of 20 000 numbers, they can be anything from 1 to 1000 000 000. I also have a bunch of other numbers and for each of them I need to find and "remove" the closest matching number from the list.

I can use binary search to find such numbers, but I really have no idea how to avoid using the same number twice and be fast enough. If the numbers were unique, I could just use a set. If I use a vector, vector.remove(index) is painfully slow.

Like where to even begin? What kind of data structure would even work, so I could efficiently search for closest matches and remove them or mark them as used..

Any reasonable binary tree will work. Removing an element from a tree is logarithmic long as the tree is balanced on creation.

If a number in the first set can be matched more than once by a number in the second set, or if you know that the "keys" will always be given in ascending or descending order, then you could sort both sets and then step through them linearly once. It might be possible to make some adaptation to that approach if you know that key collisions are rare or that the keys are approximately sorted, but I suspect that will get very annoying very quickly.

Xerophyte fucked around with this message at 13:10 on Jan 31, 2024

robostac
Sep 23, 2009
If you are using c++ (guessing based on set / vector.remove) there is a multiset structure that is probably exactly what you want ( an ordered set that allows multiple of the same values).

Another option as it sounds like set was viable without duplicates is too add tuples of (value, index) to the set as that will make all the inputs unique and you can find the closest before and after (searchvalue, 0) and ignore the index part.

Ihmemies
Oct 6, 2012

robostac posted:

If you are using c++ (guessing based on set / vector.remove) there is a multiset structure that is probably exactly what you want ( an ordered set that allows multiple of the same values).

Another option as it sounds like set was viable without duplicates is too add tuples of (value, index) to the set as that will make all the inputs unique and you can find the closest before and after (searchvalue, 0) and ignore the index part.

I was trying rust. Thanks for all the answers! Rust has only a set, no multiset, so set must contain only unique values. I ended up trying vecdeque, which seems to have quite fast removals. Figuring out how to create a binary tree out of the inputted data was a bit too complex today.

Anyways, I have a "funny" test case, where there are 200000 tickets and 200000 bids. Problem is, that 199999 tickets are price 1 and one ticket is price 2, and all bids are 1.

That means 199999 customers get a ticket, one customer doesn't get a ticket, and my binary search is way too slow because of the data is NEARLY identical. With random data it works quite fast, but the amount of binary search iterations is O(n) with that specific nearly homogenous test data.

ultrafilter
Aug 23, 2007

It's okay if you have any questions.


You can implement a multiset using a set data structure by storing pairs that consist of an element and the number of times it occurs. Might be worth looking into.

Ihmemies
Oct 6, 2012

A very bad solution was to check if the number at binary search's result index is the same as the number in first index. Then pop one index from front.

Apparently with nearly homogenous numbers, the indexes tend to set to the middle, so all removals are super slow. With random numbers the removals spread out more evenly, and are thus faster on average.

Don't do what I did, but at least it works with these specific test cases.

Bruegels Fuckbooks
Sep 14, 2004

Now, listen - I know the two of you are very different from each other in a lot of ways, but you have to understand that as far as Grandpa's concerned, you're both pieces of shit! Yeah. I can prove it mathematically.

Ihmemies posted:

I was trying rust. Thanks for all the answers! Rust has only a set, no multiset, so set must contain only unique values. I ended up trying vecdeque, which seems to have quite fast removals. Figuring out how to create a binary tree out of the inputted data was a bit too complex today.

Anyways, I have a "funny" test case, where there are 200000 tickets and 200000 bids. Problem is, that 199999 tickets are price 1 and one ticket is price 2, and all bids are 1.

That means 199999 customers get a ticket, one customer doesn't get a ticket, and my binary search is way too slow because of the data is NEARLY identical. With random data it works quite fast, but the amount of binary search iterations is O(n) with that specific nearly homogenous test data.

rust has a BTreeMap which is a balanced binary tree. maybe something like:

code:
use std::collections::BTreeMap;

fn find_and_remove_closest(map: &mut BTreeMap<i32, i32>, target: i32) -> Option<i32> {
    let mut candidates = vec![];

    // Check if target exists
    if let Some(&count) = map.get(&target) {
        candidates.push((target, count));
    }

    // Check predecessor
    if let Some((&key, &count)) = map.range(..target).next_back() {
        candidates.push((key, count));
    }

    // Check successor
    if let Some((&key, &count)) = map.range((target + 1)..).next() {
        candidates.push((key, count));
    }

    // Find the closest value to target 
    if let Some(&(closest, _)) = candidates.iter().min_by_key(|&&(key, _)| (i32::abs(target - key), key)) {
        // Decrement or remove the entry
        let count = map.entry(closest).or_insert(0);
        if *count > 1 {
            *count -= 1;
        } else {
            map.remove(&closest);
        }
        return Some(closest);
    }

    None
}

fn main() {
    let mut numbers = BTreeMap::new();
    for &number in &[1, 5, 5, 10, 15] {
        *numbers.entry(number).or_insert(0) += 1;
    }

    if let Some(closest) = find_and_remove_closest(&mut numbers, 6) {
        println!("Closest number to 6 is {}", closest);
    } else {
        println!("No closest number found");
    }
}

Foxfire_
Nov 8, 2010

Ihmemies posted:

I am quite stuck. I have a collection of 20 000 numbers, they can be anything from 1 to 1000 000 000. I also have a bunch of other numbers and for each of them I need to find and "remove" the closest matching number from the list.

I can use binary search to find such numbers, but I really have no idea how to avoid using the same number twice and be fast enough. If the numbers were unique, I could just use a set. If I use a vector, vector.remove(index) is painfully slow.
Is the 20,000 numbers problem size just a placeholder for something bigger, or is this going into something very limited/performance sensitive?

I would expect that even a naive implementation would be fast on human timescales for that small of a problem. 20000 doubles/int64 is only 160KB. That should easily fit in cache on modern CPUs and walking it shouldn't take very long at all.

I'd take a second to make sure you're measuring what you mean to first

Computer viking
May 30, 2011
Now with less breakage.

From the shape of the problem I suspect the measurement here is ultimately "what will the person grading it think of my solution"?

MREBoy
Mar 14, 2005

MREs - They're whats for breakfast, lunch AND dinner !
Anyone out there who is good with Leaflet/CSS want to make a quick US$25 bucks ? I need help stealing a single on/off checkbox.
nm figured it out, ty

MREBoy fucked around with this message at 04:57 on Feb 24, 2024

Hadlock
Nov 9, 2004

Pretty open ended question

With the release of "traditional" 52 card deck builder game balartro, how would you structure your deck/card objects, given that they can have multiple modifiers and counters added to them.

ultrafilter
Aug 23, 2007

It's okay if you have any questions.


Hadlock posted:

Pretty open ended question

With the release of "traditional" 52 card deck builder game balartro, how would you structure your deck/card objects, given that they can have multiple modifiers and counters added to them.

Ultimately that's a data modeling problem, so it's going to depend on what kind of queries you need to do and what sort of data you need to represent. Do you only need to be able to look up the modifiers for a card, or do you need to be able to find all the cards with a given modifier? Are there a small set of modifiers that won't expand, or are there (e.g.) uncapped multipliers? There are probably other questions that matter, but those are the big two that come to mind right away.

Computer viking
May 30, 2011
Now with less breakage.

It's also the sort of problem where the information is so tiny and the time constraints so loose that you should prioritise whatever you think is more pleasant to work with over what's efficient.

There's apparently something wrong with me, since I started designing an SQL schema. I don't recommend going that way, though it would definitely work. (Because most solutions would work here.)

leper khan
Dec 28, 2010
Honest to god thinks Half Life 2 is a bad game. But at least he likes Monster Hunter.

Computer viking posted:

It's also the sort of problem where the information is so tiny and the time constraints so loose that you should prioritise whatever you think is more pleasant to work with over what's efficient.

There's apparently something wrong with me, since I started designing an SQL schema. I don't recommend going that way, though it would definitely work. (Because most solutions would work here.)

the thing wrong with you is thinking there was something wrong with you :colbert:

Adbot
ADBOT LOVES YOU

pokeyman
Nov 26, 2006

That elephant ate my entire platoon.
My sql schema is an id column and a text column. The game is an append-only text log of events.

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply