Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›6 »

KillHour: Oct 28, 2007

Who likes graph algorithms?

I need to determine the connectedness of a graph as vertices and edges are added and removed. The graph has some rules:

- Graph is undirected
- Vertices are in a 2d square grid
- Vertices can be connected via any of the cardinal directions, and only if the connected vertex is in a neighboring cell
- Two vertices can only have a single shared edge
- Edges will never cross
- No loops

Here's an example of a valid graph:

Adding to the graph could be a new edge between existing vertices, or it could be connecting an entire graph with the same rules (including the trivial example of a single vertex by itself).

Removing from the graph could be removing a single edge or an entire vertex.

I need to be able to determine if the graph is still connected after a removal, and if it's not, what nodes belong to which new connected graph. I also need to be able to figure out if an addition combines two unconnected graphs into a single connected graph.

I'm mostly concerned with the time complexity of the algorithm, not the space complexity. In addition, the data is stored in an object of arrays pattern, not array of objects and could be highly parallelized if there is a good algorithm for it.

Adding and removing will be common, and both will be roughly equally as likely. I expect the graph to have a fairly large number of bridges relative to the total number of vertices and I also don't expect the graph to be very large (most would be less than a dozen vertices, hundreds of vertices is possible, but unlikely). However, I expect to have a large number of graphs - potentially hundreds or thousands.

Some approaches I've considered:

* Treat additions trivially (two graphs labeled as separate are merged by overwriting the graph associations of one of the graph's vertices and additions to a single graph have no processing beyond adding the edge to the array). Removals are handled by trying to A* pathfind from one vertex of the removed edge to the other.

Pros: Simple to implement, no additional stored data required. Additions are very fast. Can batch removals together (all edges can be removed before attempting to update the graph).
Cons: Does not take advantage of OoA data layout - lots of random access. Removals are slow. If the graph is no longer connected, A* is worst-case algorithm. Not easily multithreaded.

* Maintain list of bridges and update on additions.

Pros: Removal is trivial.
Cons: I can't find an algorithm to update a list of bridges; just generate them from scratch. Algorithm is (O)E+V, which is worse than A* (O)V. Does not take advantage of OoA data layout. Additions are slow if not connecting two previously unconnected graphs. Not easily multithreaded.

# ¿ May 24, 2020 22:52

Adbot: ADBOT LOVES YOU

# ¿ May 4, 2024 18:01

KillHour: Oct 28, 2007

ultrafilter posted:

You're interested in dynamic connectivity. The typical case assumes that the set of vertices is fixed and that only edges are added and deleted, but if you're only ever removing vertices, I think you can just remove all the edges attached to a vertex and get the same effect.

Thanks! It's valid to remove an edge by itself or an entire vertex, but I'm sure it can be adapted.

KillHour fucked around with this message at 23:42 on May 24, 2020

# ¿ May 24, 2020 23:38

KillHour: Oct 28, 2007

Pakistani Brad Pitt posted:

This is going to be a very newbish question:

I'm making an attempt to really learn object oriented programming for the first time (I'm comfortable with the more old school basic building blocks of programming like primitive variable types/conditionals/loops/whatever). So far things are going fine in absorbing various OO concepts but I have a very general question about how much I should abstract into objects that's kind of hard to google.

Say for example I wanted to make a implementation of the lovely board game Monopoly. It's very intuitive to me at a high-level that I'd want to make objects for the cards with a method for assigning them to players, an object for the board which contains Space objects for Park Place/Boardwalk, an object for the player pieces, etc etc.

The part where I'm struggling (or maybe just curious) is when I think about something like the money in the game. The old non OO programmer in me jumps at the idea that I could forego objects and keep track of money with simple variables, like:
code:
int playerOneMoney = 500;
int playerTwoMoney = 500;
and then manipulate these over the course of the game with simple arithmetic operations when the player collects money from the bank, or pays another player. I think that would work, but is it a good idea?

Should I instead be defining a dollarBill class, where I then use an instance variable to say "this is a $100 bill", and then write code which passes this bill object around to players/the bank? On one hand it seems like overkill, but on the other, maybe it makes for cleaner, more extensible and less error-prone code?

You're misunderstanding the goal custom objects are trying to solve. You don't want to create a bill object unless you actually want to keep track of every bill individually (which you may, but most implementations probably wouldn't because the math would suck). You want to create a player object so that you don't have different variable names for playerOneMoney and playerTwoMoney. Let's say you go through and implement a function to update a player's account when landing on an owned property. Without custom objects, it would look something like this:

code:

switch (currentPlayer):
	case 1:
		playerOneMoney -= rent;
		break;
	case 2:
		playerTwoMoney -= rent;
		break;
	case 3:
		playerThreeMoney -=rent;
		break;
	case4:
		playerFourMoney -=rent;
		break;
	default:
		throw new SystemException("Invalid player");

switch (propertyOwner):
	case 1:
		playerOneMoney += rent;
		break;
	case 2:
		playerTwoMoney += rent;
		break;
	case 3:
		playerThreeMoney +=rent;
		break;
	case4:
		playerFourMoney +=rent;
		break;
	default:
		throw new SystemException("Invalid player");

Ugly, right?

Now compare that to if there was a player object that can get passed around by reference.

code:

public void GetCashSon (player, owner, rent) {
	player.money -= rent;
	owner.money += rent;
}

MUCH cleaner, and you don't have to manually handle every permutation of player. If you wanted to support more than 4 players, this function could handle it with no changes at all.

e:f;b

# ¿ May 25, 2020 19:35

KillHour: Oct 28, 2007

Dominoes posted:

Use playerOneMoney as a var until you want to bundle more things with it. Keep it as simple as you can.

Objects aren't about bundling things, they're about abstracting things. Even if each player literally just has money and nothing else (which they won't), it would still make sense to put it in a player object because you know you're going to have multiple players.

# ¿ May 25, 2020 19:41

KillHour: Oct 28, 2007

I would definitely give each square an owner property of type Player so you don't have to iterate through every player's cards to find out who owns a square you landed on.

# ¿ May 25, 2020 19:52

KillHour: Oct 28, 2007

Pakistani Brad Pitt posted:

Thanks for all of the very quick answers (and the detail, KillHour/Dominoes)!

This all makes good sense to me, and I think you pretty much answered my followup, which was going to be "What if the rules of Monopoly limited the supply of money to what is physically shipped in a set?". (e.g. if you draw a "Collect $200" card, you can only collect it as 2 $100 bills if there are still 2 $100 bills in the bank, but you could also take twenty $10 bills, or 1 $100 and two $50's, etc.)

In that case, it seems like it would be a good idea to make an Bill-type object and methods to move/store them in Player or Bank owned arrays to represent the money? It seems like you could also do this by keeping a counter integer for each bill type and incrementing/decrementing it all the time to keep track?

hashmap/dictionary with the face value as the key and the quantity remaining as the value.

Objects only make sense if you're going to store information in them. The bill itself has no properties that you care about.

Edit: Yes I know empty classes and structs are a thing but I'm trying to keep it simple.

Double Edit: You might be thinking "But the bill does have a property - its value" and you could do that, but then you'd have to iterate through the entire array of bills every time you wanted to find one of a certain type. Which, I admit, is more true to the actual game, but it's really inefficient.

KillHour fucked around with this message at 20:13 on May 25, 2020

# ¿ May 25, 2020 20:04

KillHour: Oct 28, 2007

Dr. Stab posted:

Even in that case, rather that throw around bill objects, I would just make a MoneySupply object, with properties like num20, num100, etc. Then, you can write methods like totalMoney() or canMakeExactChange(). Then, give each player and the bank their own MoneySupply.

The idea here is that all the code that cares about fiddling with money goes in the money class, and other classes only need to think about money in a broad sense.

e: also, later, if you decide you need individual bill objects, you can just change the implementation of the MoneySupply class and not have to touch a bunch of different places.

This is a good way to do it. You can also give MoneySupply a method to return the quantities of each bill for displaying on screen.

# ¿ May 25, 2020 20:22

KillHour: Oct 28, 2007

taqueso posted:

surely we can use multiple inheritance more in this situation

If you really think about it, a player is also kind of a house.

# ¿ May 28, 2020 02:56

KillHour: Oct 28, 2007

The above are good. Here are some more options that might be a little more off the beaten path:

https://processing.org/
https://two.js.org/
https://www.shadertoy.com/
https://fiddle.skia.org/c/@skcanvas_paint
https://github.com/OneLoneCoder/olcPixelGameEngine/wiki

# ¿ Jun 11, 2020 00:44

KillHour: Oct 28, 2007

Bad Titty Puker posted:

Thanks for the recommendations. I've done a small amount of Javascript programming before and it's something I'd like to learn as well.

Why? Javascript is terrible.

# ¿ Jun 11, 2020 01:37

KillHour: Oct 28, 2007

Edgar Allan Pwned posted:

how can I use programming to make better things happen in my community? I'm actually thinking about gun violence, or even voting, or relief during covid.but everything I think of comes down to data collecting and I wonder if I'm not thinking of something.

gun violence - no idea. I noticed a lot of organizations try to get the youth interested in something other than guns (like music) but I guess I'm more concerned of guns in circulation and getting them out. or gang violence?

voting - if the state has a list of registered voters, you could somehow collect who has been removed over time. I know a lot of States are flushing users out.

covid - I can only imagine data collection, but of course the data is hosed anyways.

Volunteer for a nonprofit that has goals similar to yours. They always need people to do boring IT monkey poo poo and they can never afford it.

If you're looking for something big and splashy like "I made an algorithm to solve X!", you're basically looking at getting a PhD in computational sociology and going into a field that doesn't pay squat, so good luck.

KillHour fucked around with this message at 17:37 on Jul 4, 2020

# ¿ Jul 4, 2020 17:35

KillHour: Oct 28, 2007

LongSack posted:

Does anyone have a good replacement for Visio? I�ve tried to use yEd, but it�s not really what I�m looking for. Primarily I want to make application layer diagrams, say where the lowest layer is MS SQL, then above that is EF Core, then my data access layer, and so forth. yEd doesn�t handle rotating shapes, like if I want to represent a common layer along the side of the other layers since they all share common classes, models, etc. TIA

I use Lucidcharts and I like it.

# ¿ Jul 29, 2020 18:50

KillHour: Oct 28, 2007

Falcorum posted:

it made pretty graphs, which were useless for about 300 out of the 305 people using it at the company.

The thing you forget is that the 5 people who like the graphs are the only people who matter for purchasing decisions.

# ¿ Aug 22, 2020 06:37

KillHour: Oct 28, 2007

The Fool posted:

There is literally no reason to use Atom while VS Code exists.

Sublime would have better performance if that’s a concern, but if performance is a concern you should be using a jetbrains ide.

Sublime is my go to for opening massive (multi gigabyte) files. Other than that, VS Code all day long.

# ¿ Sep 8, 2020 04:55

KillHour: Oct 28, 2007

fankey posted:

Does anyone know of any tools that can be used to simulate bad TCP implementations? In particular we have some 3rd party control systems that leave our TCP servers with tons of sockets left in FIN_WAIT2 which I think might be due to their crappy microcontroller TCP stack. I have some ideas on how to solve the issue but I'd like to be able to reproduce the issue to be sure. I assume there are some hacker tools out there that can do this but haven't been able to track one down that allows this specific behavior.

This is one of those fun ones where there are a bunch of free tools that are all going to be CLI and lots of manual work and a few paid tools with nice GUIs.

https://tcpreplay.appneta.com/
http://www.hping.org/
https://scapy.net/
https://omnipacket.com/flowcoder

TCP Replay is literally just going to replay a pcap file you record of the exchange. Some basic editing capabilities, but I haven't played with them. Is that enough for what you're doing?

Personally, I like Scapy, because being able to do it all in Python is convenient and way less of a PITA than shell scripting. It has a very basic TCP automation system, but you're going to have to write most of the logic yourself.

Hping is really powerful, but the only people who use it are the kind of people who run BSD as their primary operating system. You know exactly the kind of people I mean. Maybe skip that one.

Ostinato is popular, but UDP only so nope.

Flowcoder is pretty and can do just about anything ever, but costs $Texas.

# ¿ Oct 15, 2020 06:04

KillHour: Oct 28, 2007

Python question:

I want to create a module that has a completely abstracted set of functions. Instead of defining every function, I need to be able to intercept any call and dynamically route it.

For example:

code:

import myModule

myModule.foo()
myModule.bar(arg1, arg2)

Both foo and bar should call the same function inside the module, without defining that foo or bar exists ahead of time. I should end up with something that looks like the following on the backend:

code:

interceptFunction(fName, args):
  # do stuff

The reason I want to do this is I need to pass these functions to backend libraries in a different language and I don't want to maintain a list of hundreds of functions that do nothing but forward the call and will change relatively frequently.

Edit: I think this might be what I'm looking for: https://docs.python.org/3/reference/datamodel.html#object.__getattribute__

Double Edit: Looks like that only works on classes. Any way to make it work without an instance?

KillHour fucked around with this message at 17:01 on Oct 25, 2020

# ¿ Oct 25, 2020 16:46

KillHour: Oct 28, 2007

Zoracle Zed posted:

Something like this, I think, in python 3.7+, using itertools as the target module to patch:

code:

from unittest.mock import patch

def intercept(funcname):
    print('intercepted:', funcname)
    
    def _override(*args, **kwargs):
        print('called:', funcname, args, kwargs)
        
    return _override
    
    
def test_it():
    import itertools
    itertools.foobar(666)


with patch('itertools.__getattr__', intercept, create=True):
    test_it()

This is really cool!

But I should have mentioned this is using Skulpt (the code I'm referencing is in JavaScript), so I only have ~2.6

Maybe I can dig through the implementation and just pull out the patch code....

KillHour fucked around with this message at 23:08 on Oct 25, 2020

# ¿ Oct 25, 2020 23:00

KillHour: Oct 28, 2007

Found a really simple and elegant solution:

code:

class xdmp:
    def __getattr__(self, name):
        return lambda *args : self.somethingElse(name, *args)

    def somethingElse(self, name, *args):
        print("Calling {} with args {}".format(name, args))

Trying to see if I can get the class to be the default thing you're accessing in the module (similar to exports in JS), but I can live with forcing people to use a class reference if I have to.

# ¿ Oct 26, 2020 00:10

KillHour: Oct 28, 2007

ended up just doing "from [package] import xdmp" and it works like a charm - xdmp.foo("bar", "baz") returns "Calling foo with params (bar, baz)"

# ¿ Oct 26, 2020 03:35

KillHour: Oct 28, 2007

Make sure you make a :krad:

chiptune to go with it.

# ¿ Nov 11, 2020 04:51

KillHour: Oct 28, 2007

Yeah, cracktros kind of started the demo scene. I think Pouet.net is still a thing. I bet they have tons of people there with far more specific knowledge of this stuff.

# ¿ Nov 11, 2020 06:20

KillHour: Oct 28, 2007

What are you using for schema management? JSON doesn't natively have a specific schema format and there are about a billion competing standards.

Edit: Oh, this one https://json-schema.org/

# ¿ Nov 13, 2020 21:42

KillHour: Oct 28, 2007

leper khan posted:

I'm getting vibes about them not giving you a machine.

# ¿ Nov 19, 2020 02:53

KillHour: Oct 28, 2007

If you're trying to hide super secret proprietary algorithms from competitors, I probably wouldn't put them in python. Write your secret stuff in C++ and compile a dll the Python code can call. It won't stop someone with Ghidra and a lot of free time, but it should be good enough.

# ¿ Nov 27, 2020 21:28

KillHour: Oct 28, 2007

omeg posted:

It can be changed, just probably not in the time frame I've got realistically if the changes are too drastic. There's a lot of academic grade code in there.

It is a web app but it will be deployed without internet access

It sounds to me like whatever security issues you think you have are probably dwarfed by the ones you actually have and don't know about.

# ¿ Nov 28, 2020 06:47

KillHour: Oct 28, 2007

We recently switched to an enforced linear history with rebase commits instead of merge commits, and it's a pain in the rear end, but gives us much better histories. We also switched to a monorepo, which I hated when it was suggested and still hate now.

Basically, Git sucks and both merge commits and rebase commits have downsides. Pick the least-worst option for you.

# ¿ Nov 30, 2020 16:56

KillHour: Oct 28, 2007

I would strongly consider only doing rebase commits on a monorepo. Merge commits are a great way to gently caress up someone else's project unintentionally.

# ¿ Nov 30, 2020 17:15

KillHour: Oct 28, 2007

Yes, we only do rebase commits and the repo is configured to not let you push any merge commits (you'll get an error if you try). We've never had an issue with lost work. The only thing that comes up regularly is you'll open a PR and by the time it gets approved, master has been updated by someone else so you'll have to rebase again. Mildly annoying, but not a huge deal. The only really annoying thing is if you mess up and accidentally do a merge commit (or rebase the wrong direction), the repo won't let you just revert it - you have to hard reset. You learn not to do that quickly enough, though.

# ¿ Nov 30, 2020 17:51

KillHour: Oct 28, 2007

Git is a great example of something being really clean and elegant in theory, but then reality hits and it ends up with all sorts of crap tacked on to make it work for the specific things people want to do with it.

I'm personally waiting for the inevitable 'disruption' to happen where everyone decides monorepos suck and microrepos are the ~~future~~.

# ¿ Nov 30, 2020 18:08

KillHour: Oct 28, 2007

Dominoes posted:

Personally, I categorize a non-superficial understanding of Git with Haskell: Elegant in theory, but I've never been able to Grok it. It feels too... academic? Built by and for people who think in a different way than I'm accustomed to.

It was created by the kind of guy who makes his own OS "for fun" because none of the existing ones are ideologically pure enough. Theoretical beauty over practical reality is kind of the point.

I use the GitHub Windows GUI thing and it is good enough for 99% of what I do with it. :shrug:

Edit: Also, it was written specifically for managing the Linux kernel code. All the other stuff companies use it for weren't really in the original design, so don't think I'm blaming Linus for what it became.

KillHour fucked around with this message at 18:30 on Nov 30, 2020

# ¿ Nov 30, 2020 18:28

KillHour: Oct 28, 2007

The Fool posted:

I use the git integration in VS code and that�s good for 99% of the stuff I need to do.

Can confirm; VS Code is the best thing Microsoft ever did after the Pipes 3D screensaver.

# ¿ Nov 30, 2020 18:33

KillHour: Oct 28, 2007

raminasi posted:

I just can't shake my hunch that the people who say things like

and the people who lament getting their repos into unrecoverable states are largely the same people. It's good enough...until it isn't.

They are, but it's Git's fault for being opaque. It's way too easy to break something in a confusing way, and the terminology around all of it doesn't help.

# ¿ Nov 30, 2020 19:30

KillHour: Oct 28, 2007

Munkeymon posted:

Excel gets closer to one with every release

Excel is already Turing complete and so is PowerPoint, for that matter.

# ¿ Nov 30, 2020 20:46

KillHour: Oct 28, 2007

Also, does TIBCO StreamBase count?

# ¿ Nov 30, 2020 21:10

KillHour: Oct 28, 2007

ultrafilter posted:

The general rule of thumb is to use a for loop when you know how many iterations the loop will take, and a while loop otherwise. Iterating over all the elements of a collection is always in the former case (although you probably want to use comprehensions if you can for performance reasons).

Unless you modify the collection within the loop! :viggo:

Don't do this

Okay, you might want to do this if it's a queue or something, but you won't need to do this until you're a lot more experienced. For now, don't do this.

# ¿ Dec 2, 2020 15:45

KillHour: Oct 28, 2007

CarForumPoster posted:

Agree for a list but is extremely common and necessary to loop over a pandas dataframe, modifying the elements in the rows.

Modifying the elements in a loop is extremely common. Modifying the collection by adding or removing elements is not, and is the source of many bugs.

# ¿ Dec 4, 2020 05:37

KillHour: Oct 28, 2007

CarForumPoster posted:

Yea agree that modifying the number of things you�re looping over within the list is a big red flag in code. Our new to python friend might not know the difference yet though.

Which is why I wanted to call it out as something not to do, but thank you for helping clarify if it wasn't totally clear what I meant.

# ¿ Dec 4, 2020 05:52

KillHour: Oct 28, 2007

Kaggle?

# ¿ Dec 8, 2020 18:46

KillHour: Oct 28, 2007

A QR code is usually literally a link to a website, so do that.

waitlist.com/somevendorcode

When you visit the site, it puts you in line and tells you when you're up. Done.

# ¿ Dec 18, 2020 19:53

Adbot: ADBOT LOVES YOU

# ¿ May 4, 2024 18:01

KillHour: Oct 28, 2007

You're going to have to define what you mean by "similar" in a very specific way. Do you mean fewest changed letters? Do you mean most words in common? Do you mean similar in meaning? Do you mean similar in writing style? What is the high-level problem you're trying to solve?

# ¿ Jan 13, 2021 01:46

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›6 »