|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
Speaking of maths... Do any of you know if there's an existing algorithm for slicing an array into as many batches of n size or as many n and n - 1 size batches (trying to avoid batches of size n - 2 or less if possible if array count % n is nonzero while at the same time maximizing the amount of size n batches).
eg:
10 -> 5, 5
11 -> 4, 4, 3
12 -> 4, 4, 4
13 -> 5, 4, 4
14 -> 5, 5, 4
15 -> 5, 5, 5
16 -> 4, 4, 4, 4
17 -> 5, 4, 4, 4
18 -> 5, 5, 4, 4
19 -> 5, 5, 5, 4
20 -> 5, 5, 5, 5
and so on...
Edit: So far I came up with this hacky solution I put together ad hoc.
PLAYERS_COUNT = 256
TABLE_MAX = 5
OUTLIERS = {
7 => [4, 3],
8 => [4, 4],
9 => [5, 4]
}.freeze
def find_divisions(num)
remainder = num % TABLE_MAX
return get_tables_for(num) if remainder.zero?
return OUTLIERS[num] if (num < 10)
# up the remainder to maximize table size and even spread
remainder += num < 20 ? 2 : 1 if remainder < 2
remaining_players = TABLE_MAX + remainder
tables = find_divisions(num - remaining_players)
return tables + OUTLIERS[remaining_players]
end
def get_tables_for(players)
Array.new(players / TABLE_MAX, TABLE_MAX)
end
def final_tables(ary)
return ary unless (ary & [5, 3]) == [5, 3] # find if both 5 and 3 present
# remove 5 and 3 from array to turn it into 4, 4
ary.slice!(ary.index(5))
ary.slice!(ary.index(3))
ary + [4, 4]
end
puts final_tables(find_divisions(PLAYERS_COUNT))
|
Hyrule18967 Posts
Sounds like a fun challenge. Is the aim to maximize slices of size n or minimize slices of size n - (i >1)?
There's some immediately easy cases, like L % n == 0, L % n == n - 1, and L == n
Anyway, it's fairly similar to the pie problem in concept.
For code I found this but it's a minimization of difference rather than targeting a specific slice size.
|
On January 08 2022 12:12 Manit0u wrote:
Speaking of maths... Do any of you know if there's an existing algorithm for slicing an array into as many batches of n size or as many n and n - 1 size batches (trying to avoid batches of size n - 2 or less if possible if array count % n is nonzero while at the same time maximizing the amount of size n batches).
eg:
10 -> 5, 5
11 -> 4, 4, 3
12 -> 4, 4, 4
13 -> 5, 4, 4
14 -> 5, 5, 4
15 -> 5, 5, 5
16 -> 4, 4, 4, 4
17 -> 5, 4, 4, 4
18 -> 5, 5, 4, 4
19 -> 5, 5, 5, 4
20 -> 5, 5, 5, 5
and so on...
This sounds like an instance of the 'Change-making problem', where the values of the coins are n, n-1, and n-2.
See: https://en.wikipedia.org/wiki/Change-making_problem
Now I'm wondering if there's quicker ways to do it given these specific values.
EDIT: I guess this would need a slight tweak if for example [5,4,4] is preferred over [5,5,3] for 13.
|
I came up with the solution that seems to work. And yes, the idea is to maximize the number of slices of size 5 and minimize the amount of slices of size 3 where 5, 4, 4 is preferred to 5, 5, 3.
I'm working on an algo that will generate player seating at the tables in a tournament so I need to divide the players. After that I'll be doing swiss etc.
Current software they're using for this is absolutely atrocious (an excel spreadsheet with thousands of hardcoded seating variables etc.).
|
Hyrule18967 Posts
Ah. You could look into simulated annealing but that's probably a bit (a lot) overkill.
|
Yeah, it's just something I'm doing for fun that may be useful to some people in the future. Also, there isn't really a big need for some super optimized algos here as you'll never really need to solve it for more than 500 players I think.
|
On January 08 2022 15:44 Manit0u wrote:
Yeah, it's just something I'm doing for fun that may be useful to some people in the future. Also, there isn't really a big need for some super optimized algos here as you'll never really need to solve it for more than 500 players I think.
Isn't it simply the case that, in general, you solve it optimally with ceil(L/n) groups, of which n - L%n groups of size n - 1, and the rest of size n?
There are a number of corner cases: if L%n = 0, then you need L/n groups of size n. If n - L%n > ceil(L/n), there is no solution, so pick a different n. A special case arises for n - L%n = ceil(L/N). In that case you have 0 groups of size n, and all of size n-1. You can either treat that as an okay solution, or as an exception, up to you.
Otherwise, if L/n < 2 then you just need to pick a smaller n, or the optimal configuration of L/2 (if L is odd then one floor, one ceil, obviously)
This gives you the groups and their sizes and then slicing the array is a quick loop over the groups.
E: an example:
L=9.
n=2
L/n = 4.5, so 5 groups
n - L%n =1
1 group of size 1, and 4 of size 2.
n=3
trivial
n=4
L/n = 2.25, so 3 groups
n - L%n = 3
3 groups of size 3, 0 of size 4.
n=5+
L/n = 1.8, so 2 groups
Trivial solution:
1 group of size 4, 1 of size 5
E2: I removed one of the boundary conditions when working on the example, but it is just a quirk of the example, so added it back in. An example of the problematic case is for instance L=20 and n=8. Here ceil(20/8) = 3, but 8 - 20%8 = 4. So it breaks down.
If you absolutely need a solution in those cases, what you can do is accept a single group of size n-2 and try again for L-n+2. For the example above this would lead you to the solution 7,7,6. Or, if you reject the boundary condition as well, then 8,6,6. However there are still cases it breaks down, e.g. L=20 and n=9. You'd need an extra check for n>L to call it recursively (and it'd give you 7,7,6 as the solution if you added that check.
However, all of this is only for the weird cases (generally when L/n gets close to 2).
|
I really need it for n=5 (no higher than that). I'll tinker around a bit with it.
|
Then hardcode it until L = 11 and above it is trivial?
|
On January 08 2022 12:12 Manit0u wrote:Speaking of maths... Do any of you know if there's an existing algorithm for slicing an array into as many batches of n size or as many n and n - 1 size batches (trying to avoid batches of size n - 2 or less if possible if array count % n is nonzero while at the same time maximizing the amount of size n batches). eg: 10 -> 5, 5 11 -> 4, 4, 3 12 -> 4, 4, 4 13 -> 5, 4, 4 14 -> 5, 5, 4 15 -> 5, 5, 5 16 -> 4, 4, 4, 4 17 -> 5, 4, 4, 4 18 -> 5, 5, 4, 4 19 -> 5, 5, 5, 4 20 -> 5, 5, 5, 5 and so on... Edit: So far I came up with this hacky solution I put together ad hoc.
PLAYERS_COUNT = 256
TABLE_MAX = 5
OUTLIERS = {
7 => [4, 3],
8 => [4, 4],
9 => [5, 4]
}.freeze
def find_divisions(num)
remainder = num % TABLE_MAX
return get_tables_for(num) if remainder.zero?
return OUTLIERS[num] if (num < 10)
# up the remainder to maximize table size and even spread
remainder += num < 20 ? 2 : 1 if remainder < 2
remaining_players = TABLE_MAX + remainder
tables = find_divisions(num - remaining_players)
return tables + OUTLIERS[remaining_players]
end
def get_tables_for(players)
Array.new(players / TABLE_MAX, TABLE_MAX)
end
def final_tables(ary)
return ary unless (ary & [5, 3]) == [5, 3] # find if both 5 and 3 present
# remove 5 and 3 from array to turn it into 4, 4
ary.slice!(ary.index(5))
ary.slice!(ary.index(3))
ary + [4, 4]
end
puts final_tables(find_divisions(PLAYERS_COUNT))
Lol, just looking at this makes me feel stupid. What do you want to achieve with this algorithm?
|
This algo is pretty straightforward. It gets all the possible slices of 5, adds the remaining spreads for 7,8 or 9 and tries to get rid of slice of 3 if there's available slice of 5 to even it out.
|
Hyrule18967 Posts
Less programming but still awesome: a friend gave (!) me some Cisco gear. 4x 2702i WAPs, an AP1810W-E-K9, and a 4321 switch. I've been told at least on of the 2702s works. Also, my work gives me courses on Udemy so CCNA might be in my future. Just waiting on a PoE injector and a USB->serial rj45 cable so I can start messing with them.
+ Show Spoiler +
|
Northern Ireland23663 Posts
Still an awful programmer
Have secured a decent full stack placement gig with some folks called Puppet which I’m happy enough with, then after that year it’s final degree year which, looking at it should be piss easy with the (optional) year in industry. Looking at the final year syllabus and what I’m expected to do in my prospective workplace, the latter is far more involved, so if I can navigate that I’m sweet.
I’m pretty proficient in Java, so the Ruby I’m expected to work with (from a vague half assed look) seems pretty intuitive. There’s some front end stuff with React, I’ve had minimal exposure to scripting languages, and a lot of stuff with Golang that I’m not familiar with at all.
Was curious if any of you folks had any books you’d recommend? I know online tutorials and resources exist, but I do enjoy a good book, just to chill out with and thumb through. I find it easier to focus sometimes just learning from a book.
Particularly computing architecture, general structuring of algorithms in a non-language specific sense, and hey whatever you folks think is cool.
Thanks in advance
|
|
|
Hyrule18967 Posts
Serial-USB cable and PoE injector were delivered today so I got started on the gear. Managed to (probably) factory reset the router, still have some weirdness with the APs. Everything I read about factory resetting them says to hold mode, power on, wait for amber light, release...but I get no amber light. I did find a different method which reset the default credentials and restored the default config, except there's still a bunch of VLANs set up and it's not able to talk to the router.
Going to have a long futz-with-stuff session on Saturday, maybe I'll get it all working then.
|
|
|
Northern Ireland23663 Posts
Cheers folks! Look like the kinda thing I’d be looking for
|
On January 12 2022 18:50 WombaT wrote:
Still an awful programmer
i respectfully suggest not labelling yourself sir. Please, just code and enjoy the journey. Please don't dwell on failures and don't beat yourself up when things go wrong. Other coders at the same place may be protecting their turf and will use every trick in the book to make you look dumb in front of management.
Software Projects Everywhere are Totally Fucked
Generally speaking, software development projects are so poorly managed you'll have plenty of time to learn before a significant number of management clones in authority discover you don't know what you are doing. That is assuming you, currently, don't know what you are doing. If you are not as bad as you think you are... all the better.
https://www.amazon.ca/Inmates-Are-Running-Asylum-Products/dp/0672326140
the author's experiences in corporate America to illustrate how talented people continuously design bad software-based products and why we need technology to work the way average people think.
Imagine, at a terrifyingly aggressive rate, everything you regularly use is being equipped with computer technology. Think about your phone, cameras, cars-everything-being automated and programmed by people who in their rush to accept the many benefits of the silicon chip, have abdicated their responsibility to make these products easy to use. The Inmates Are Running the Asylum argues that the business executives who make the decisions to develop these products are not the ones in control of the technology used to create them. Insightful and entertaining, The Inmates Are Running the Asylum uses the author's experiences in corporate America to illustrate how talented people continuously design bad software-based products and why we need technology to work the way average people think. Somewhere out there is a happy medium that makes these types of products both user and bottom-line friendly; this book discusses why we need to quickly find that medium.
Check out Patrick Wyatt's blogs about how poorly Blizzard managed software projects in the 90s. Its hilarious man.
https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft
From a software project management perspective, Blizzard was a shit-show in the 90s; it still grew by leaps and bounds.
So don't fret man.. there are lots of people around you and above you making lots of mistakes. Errors and mistakes are part of the process. There are probably some errors in this post about mistakes. 
|
Northern Ireland23663 Posts
On January 24 2022 02:43 JimmyJRaynor wrote:i respectfully suggest not labelling yourself sir. Please, just code and enjoy the journey. Please don't dwell on failures and don't beat yourself up when things go wrong. Other coders at the same place may be protecting their turf and will use every trick in the book to make you look dumb in front of management. Software Projects Everywhere are Totally FuckedGenerally speaking, software development projects are so poorly managed you'll have plenty of time to learn before a significant number of management clones in authority discover you don't know what you are doing. That is assuming you, currently, don't know what you are doing. If you are not as bad as you think you are... all the better. https://www.amazon.ca/Inmates-Are-Running-Asylum-Products/dp/0672326140
the author's experiences in corporate America to illustrate how talented people continuously design bad software-based products and why we need technology to work the way average people think.Show nested quote +Imagine, at a terrifyingly aggressive rate, everything you regularly use is being equipped with computer technology. Think about your phone, cameras, cars-everything-being automated and programmed by people who in their rush to accept the many benefits of the silicon chip, have abdicated their responsibility to make these products easy to use. The Inmates Are Running the Asylum argues that the business executives who make the decisions to develop these products are not the ones in control of the technology used to create them. Insightful and entertaining, The Inmates Are Running the Asylum uses the author's experiences in corporate America to illustrate how talented people continuously design bad software-based products and why we need technology to work the way average people think. Somewhere out there is a happy medium that makes these types of products both user and bottom-line friendly; this book discusses why we need to quickly find that medium. Check out Patrick Wyatt's blogs about how poorly Blizzard managed software projects in the 90s. Its hilarious man. https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraftFrom a software project management perspective, Blizzard was a shit-show in the 90s; it still grew by leaps and bounds. So don't fret man.. there are lots of people around you and above you making lots of mistakes. Errors and mistakes are part of the process. There are probably some errors in this post about mistakes.
Cheers man, some interesting reading in there for sure. Much obliged
I think the ‘terrible’ part will be somewhat mitigated in my placement year in industry, where I fluked a pretty decent gig. Can actually do it full time and throw myself into it vs the current state of affairs where I’m working far too much just to fund and do the minimum to be doing decently at my degree.
When I actually do have rare moments to properly grind I find I can pick things up alright, and also enjoy the process but they’re fewer than I’d like
|
|
|
|
|
|
|
|
EPT![[image loading]](https://i.imgur.com/pgsXe53.jpg)
