itch.io

I've been thinking about it, and I think I can put in some puzzles.  The player might miss some of them, but that's not the end of the world.

I've started on it, but right now all you can do is wander around and pick up a tent.

Thanks.  That's a lot of good information, but it's going to take me a while to read through it.

I don't really use discord, but I'm planning an exploration game inspired by the Great Race of Mercy with fantastical elements.  I'm not going to spend two whole months on this, so it's going to be limited.

I want to have it be more of a survival game with exploration.  So you have to search to find wood for torches and campfires to survive the cold darkness.  And you have to find food.  And you have a dogsled to get to the city of Uruk and deliver diptheria antitoxin.

This is more of an experiment in text adventures than a main project for me.

Does anyone have any advice about how to make puzzles for a text adventure?  That isn't really my thing.  I planned to have my adventure be surviving to get from A to B.

I can put puzzles in the game, but I'm not sure how to make "text adventure puzzles".  It seems to me like puzzles in adventure games are usually just "find the widget to get through the door".

Fair enough.  I probably should have made that clear in the text.  What I meant was that if you could solve an NP-complete problem fast enough that you could also solve integer factorization problems.  Even though it's probably not NP-complete, it's definitely in NP.

Nondeterministic November 2 has officially started!

I'm planning to make a tool that performs stochastic search on various NP-complete problems, but I'm still finishing my attempt to submit to another jam that's ending.  I've got a bad feeling that other jam isn't going to get a submission from me at this point.

Good luck!

Neither one of those things are prohibited by the rules, so you should be fine.

I like the idea in principle, but my game might be a text editor.

Here's my jam: Nondeterministic November 2 - itch.io

This is my second attempt at creating a jam to get people interested in NP-complete problems.  The idea here is that maybe a lot of people working on NP-complete problems might learn something new that the big dogs in the world of computer science haven't discovered yet.

My own interest in this is that I might be able to make a toolbox of algorithms that I can use in my own programs.  Other people might have different objectives.

NP-complete problems include: boolean satisfiability, subset sum, sudoku, clique finding, graph coloring, and many more.

Voting shouldn't start until after the jam ends.

That's beyond what I even attempt.

I'm going to have go with the following:

Dungeon Master (video game) - Wikipedia

Tales of Aravorn: Seasons Of The Wolf on Steam (steampowered.com)

SKYHILL on Steam (steampowered.com)

Marble Age on Steam (steampowered.com) (haven't beaten the remastered version)

Pool of Radiance - Wikipedia

DROD RPG: Tendry's Tale on Steam (steampowered.com)

I play a lot of RPGs and strategy games.  Sadly, I usually don't complete the really hard ones.  I wish I could put Angband on here.  I especially wish I could Bard's Tale 1 on here, but I used an item to open a door and then stupidly saved the game without the item.

Edit: Forgot about Sunrider: Mask of Arcadius on Steam (steampowered.com)

This is perfect.  I'm going to make a game that uses a PETSCII and other character set "art" to make some sort of interactive fiction.  I'm not sure if I can actually pull it off or if it will actually be "hard".

But I'm going to learn JavaFX at the same time.

I think I'll be ready to start working on this by the time the jam's over.

I have a lot of nothing done so far.  Today was the day when I had time, and I played The Enchanted Cave 2 instead of doing anything useful.  I'm probably not going to finish a project, so I apologize for wasting your time.

But I never actually asked you for any sounds, so I guess it doesn't matter.

Hey, your soundcloud link is dead.  I have my own portfolio at: Video Game Development (lootsmuggler.com) .  The problem with it is that none of the games are playable any more.

I'm a programmer.  I plan to write the text such as it will be.  I also plan to generate some artwork with a program and find some on the internet.  I don't know what music or sound effects I need.  I'm willing to take what I can get.  There's no pay, but it'll help you add a video game to your portfolio.  However, it'll be more of a game demo.

The demo game for this jam is going to be a fantasy RPG that is mostly text-based.  It will most likely be incomplete.  I have nothing to show at this point.  The plot is that you're trying to get your son onto a boat to avoid the darkness of a night that lasts for months at a time.  You have journals that you can write messages to each other in (to satisfy the theme).  A band of heroes is killing a dragon, and that disrupts the entire local economy.

After the jam is over, I plan to eventually make a more full-featured game, but this jam demo game is more like a prototype.

Edit: Technically, your link works.  There just aren't any sounds there.  The vimeo link has sound.

Well, there's roughly 2.5 days left.  I haven't done nearly as much as what I had planned for my own project.  I feel like 1 more day of solid work will get it up to the bare minimum level I deem acceptable, but I've had difficulty making the time.

I had planned to solve a bunch of problems in several different ways, but it looks like I'm just going to have partition and maybe subset sum.

Anyways, good luck to everyone.

I updated the rules section of the jam page to mention .pdf files, but I made it more a recommendation than a rule.  It's a non-ranked jam with 6 participants so far.  I don't want to make unreasonable formatting demands.

You can create an itch project as normal, but submit a .pdf file instead of computer code or a .exe.

I believe that google doc can export documents as .pdf files.

I guess it doesn't have to be a .pdf file, but that's what I've seen in tabletop rpgs on itch.io.  Edit: I realize that this isn't about tabletop rpgs, but I think the same file format is fine.

Most people agree with your statement in general, but it's still an open question.  I used to have an interest in prime numbers, and I would like to point out a couple of things that you may not be aware of.

From Integer factorization - Wikipedia :

No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a b-bit number n in time O(b^k) for some constant k. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P.  The problem is clearly in class NP, but it is generally suspected that it is not NP-complete, though this has not been proven.

I copy-pasted this text from the middle of a wikipedia entry because I feel like they explain it better than I can.  Basically P <= Integer Factorization <= NP, but P and NP may or may not be equal.  Most people believe that P != NP because a lot of smart people have written algorithms to solve NP-complete problems and weren't able to solve them in polynomial time.  On the other hand, a lot of even smarter people have tried to prove that P != NP, and they all have failed.

What that says to me is that no one has a good answer.  I'd like to point out that I can't think of a polynomial time algorithm that's slower than O(n^3).  If no one's ever written a O(n^15991) algorithm, how can anyone say anything about what a such an algorithm might be able to do?  No human could ever write such an algorithm, but maybe there's some loophole that lets such an algorithm solve integer factorization problems.

I can beat the algorithm you described in two different ways that I already know about.

First, you only go up to square root of n [which I'll call sqrt(n)], not n/2.  

Assume n = a * b for some a and b.
We may assume without loss of generality that a <= b.
(This just makes this text simpler.  One of them <= the other.  It doesn't matter which.)
If both a and b were less than sqrt(n), then a * b < n.
If both a and b were more than sqrt(n), then a * b > n.
So a <= sqrt(n) <= b
If n has any factor other than 1 or n, it must have a factor <= sqrt(n).
If that factor is composite, then it has a prime factor even less than it.
So any composite number has a prime factor less than or equal to sqrt(n).
So we only need to check prime numbers less than or equal to sqrt(n).

Second, it's possible to combine primes, reducing the number of trial divisions (though typically at the cost of memory).

For instance, let's look at 2 and 3.  Their product is 6.  When you divide any number by 6, you get a remainder.

Remainder   Divisible by

0                   6

1                   Neither 2 nor 3

2                   2

3                   3

4                   2

5                   Neither 2 nor 3

This works because of modular arithmetic, but I'm not going to explain beyond that.  You could multiply more than 2 prime numbers together or use multiple sets of pairs of primes.  This hasn't produced a significantly better solution, but there's other options beyond what you describe.

Another similar problem, primality testing, used to be solved in the same manner.  But a better solution has been found.  The AKS primality test - Wikipedia runs in polynomial time.

Maybe something similar will happen with integer factorization.  Or maybe the boundary between polynomial and exponential just happens to be between primality testing and integer factorization.

Edit: Fixed the quotes slightly.

It's almost time to start, everybody!  Don't get too stressed out if you don't make some major breakthrough.  People have been working on this for decades.

I think I'll start with a snack.  Then, I'll work on partition first.

Factoring integers is clearly within the complexity class NP, but there isn't a proof that it's NP-complete.  I'm not going to say a lot about this, but it should be fair project for the jam.  Proving that it is or is not NP-complete is a worthwhile project.

Or someone could just write a factorization algorithm.

This is really an algorithm jam, not a game jam.  I want to spend the month of November working on NP-complete problems.  Computer science professors act like these problems are constantly popping up.

I want to zerg swarm these problems in the hopes that someone finds some cool solution, but my reddit posts have only netted 3 participants so far.  This jam is intended for normal programmers who have some knowledge of NP-complete problems but don't have PHDs.  I'm counting on the power of 1000 code monkeys to stumble across things no one has noticed.

Hypothetically, someone might find some use for these in games.  My goal for November is to create an open source toolkit that I can use to solve special cases of NP-complete problems.  I would like to model procedural generation as a boolean satisfiability problem, but I have neither procedural generation nor a game.  Yes, my plans are backwards, but Nondeterministic November has alliteration.

Here's some examples of fun projects to work on for this jam:

• Solve an NP-complete problem.
• Convert an NP-complete problem into another NP-complete problem.
• Prove that a problem is or isn't NP-complete.
• Write a mathematical proof of whether P=NP or not.
• Find some new application for an NP-complete algorithm.
• Allocate more computing resources to an NP-complete problem.  For instance, this could be using the graphics card to perform mathematical computations.  Or it could be multi-threading or using a network of computers.

For more information, visit the jam:

Nondeterministic November - itch.io

There's a whole giant list of NP-complete problems at https://en.wikipedia.org/wiki/List_of_NP-complete_problems

I haven't had a chance to figure this one out yet.

The input is a multiset, S, of positive integers.  The goal is to partition the set into 2 subsets where the sum of the numbers in the first subset is equal to the sum of the numbers in the second subset.

A video: https://youtu.be/7BynUy5ml0I

There is a dynamic programming solution to this problem.

Job sequencing is a bit complex.  I'm not going to try to explain it.

I found a video: https://youtu.be/MIvWBI8Xlyk

There seem to be multiple versions of this problem going around, and I'm not sure which one's the best to work on.

The input is a list of n items that have a weight, w[i], and a value v[i].  Also, there is an integer maximum weight for the knapsack.  The goal is to make the highest value list of items where the total weight of the items is at most the max weight.  In other words, the sum of values should be maximized, but the sum of the weights can be at most the maximum weight.

It's "0-1" knapsack because each item is included either 0 or 1 times.

Here's a video: https://youtu.be/xCbYmUPvc2Q

This problem can be solved by dynamic programming.

Subset sum is a special case of this.  A video for subset sum: https://youtu.be/C0xiOGhS_js

The input is a set T and a set U, where U is a subset of TxTxT.  In other words, U is set of triples, where each triple's elements are from the set T.  The goal is to find a set W that is a subset of U such that W is the same size as T and no 2 elements of W agree in any coordinate.

I've seen a different version of this, and I'm not sure what to do with it.

The inputs are a graph, G, and a list of terminal vertices.  The goal is to create a subtree that spans all the terminal vertices.  The non-terminal vertices may or may not be included in the subtree.  There will always be such a subtree.

This is similar to minimal spanning tree, but it's harder because not all vertices have to be included.  It's permitted to have weighted graphs for this problem, in which case you should look for the minimum tree that spans all the terminal vertices.

Here's a video: https://youtu.be/BG4vAoV5kWw

I'm confused about this problem, so I'm not going to try to describe it.  It doesn't seem like anyone uses it.

I'm not familiar with this one either.  Maybe someone else will have an explanation.

The inputs are a graph G and an integer k.  The goal is to color all the vertices with at most k colors in such a way that no 2 adjacent vertices have the same color.  It's possible that there may be no such coloring.

Here's a video: https://youtu.be/3VeQhNF5-rE

Given a graph G, a Hamiltonian circuit (a.k.a. Hamiltonian cycle) is a circuit that visits every vertex exactly once.  This problem is to find a Hamiltonian circuit or determine that there are none.

The only difference between the 2 problems is that problem 9 is a directed graph, and problem 10 is an undirected graph.

Here's a video: https://youtu.be/AamHZhAmR7o

This is another one I don't know anything about.

I don't know.  I don't know anything about  it, but it is 1 of Karp's problems.

In node cover (also known as vertex cover), the input is a graph G.  The goal is to find a set of vertices such that every edge touches one of the vertices in the set.

Here's a video about it: https://youtu.be/1KkT7y8nxH0

In set cover, the input is a set U and subsets S1, S2, ..., Sm.  The unions of the subsets must be U.  The goal is to find the smallest collection of subsets such that they include all the elements of U.

Here's a video about it: https://youtu.be/XmW3xR-0CSE .  This video includes an explanation of how set cover and node cover are basically the same.

Exact cover is a lot like set cover.  It has the set U and subsets S1, S2, ..., Sm.  However, the collection of subsets chosen must not contain any of the same elements.  Each subset in the exact cover must be disjoint from every other subset in the cover.  The exact cover does not need to be the smallest collection like in set cover.

This video is relevant to exact cover: https://youtu.be/_cR9zDlvP88

In this problem, there's some giant set U.  There's also a list of subsets S1, S2, S3, ..., Sn and an integer k.  The goal is to determine whether there is a list of k subsets that are pairwise disjoint, meaning none of them contain the same element.

I couldn't find a good video.

In this problem, the input is an undirected graph and an integer k.  If there is a clique of size k, return true.  If there isn't a clique of size k, return false.

A clique is a group of nodes that are connected to eachother by edges.

I found a video about it: https://youtu.be/B801ZELDFZo

The weird thing about this is this variation of the problem is kind of useless.  It's more useful to find the size of the largest clique, but that's not "official" problem for the purpose of NP-completeness.

I have a hard time with integer programming, so I'm not going to say anything about it.  My understanding of it is that the input is a system of polynomials with variables that have unknown values.  Each variable can be only 0 or 1.

Karp's list of NP-complete problems mentioned a matrix and a vector.  I think he was talking about the same thing, but I'm not sure.

Maybe someone else with a better grasp of this problem will explain it.

This is the original NP-complete problem (Karp's problem 1).

In this problem, the input is a boolean formula written in conjunctive normal form (CNF).  The output is either an assignment of boolean values that makes the boolean formula true of an elaborate proof that there is no satisfying assignment.

It turns out that it's possible to express any CNF formula in such a way that each clause contains only 3 literals.  In that case, it's a different variation of the problem: 3-sat (Karp's problem 13).

Here is a youtube video describing the problem: https://youtu.be/sCxmi9ZLmdc

There's a mountain of information available about boolean satisfiability.  There's no easy way to summarize it.

I personally would be more interested in a sat solver that took any propositional formula as an input and solved it without necessarily converting to CNF.  Converting disjunctive normal form (DNF) to CNF for satisfiability would be stupid, but I've been told that it's not as big of a deal as I think.  My instinct is that working on this particular version of satisfiability may be making the problem harder, but there isn't any solid evidence to back that up.