/sci/ - Science & Math

bump

would a straight-up brute force tree search not work?

>>3130018
A colleague of mine set up a brute force algorithm. He said it'd take longer than the age of the universe to check each guess. Seeing as he programmed the algorithm in Java, I don't doubt him. Yes, I have to use Java.

>>3130039
really? cuz you "only" have (n choose k) options for each column (n = nr. of cells, k = nr. of colored cells) and then that gets even further reduced as you get more columns filled in due to the line restrictions.

but yeah, i'm primarily a math guy, i tend to not care about running times.

>>3130062
> math guy, i tend to not care about running times.

if you're using "math guy" as an excuse for that.. well, you're ignorant as well as pathetic.

>>3130100
what do you mean? i don't program, i don't need to actually see a solution, i just need to know that one exists.

>>3130110
asymptotic analysis of the complexity of algorithms is math. Trying to make out this image where don't know about complexity is harmful.

i never knew how to solve those fuckers

bump for interest

>>3130039
I think he is very wrong. Make the effort to post his code and I'll make the effort to show how it is wrong.

Brute force with optimizations should work just fine.

<----- Hey faggots solve this one

> Yes, I have to use Java

what?

is this a homework thread?

>>3130125
Can't post it, sorry. He didn't show it to me, but from what he explained, it sounded very poorly optimized.
>>3130137
Two solutions exist. Cbf posting them.

>>3130137
I see what you did there

>>3130139
Yes, this is a homework thread. If it makes you feel any better, my question is outside the scope of my course. More or less, this is about satisfying my curiosity and getting marks doing it. Also, I just want to know an algorithm. Coding is the fun part.

It is simple.

I'll give you a start and you can go on from there.

First you balance the row side. In your example

xxxxx
xx
xxx
xx
xxxxx

So this makes the column side unbalanced in following fashion
0,3,0,0,-3

so whenever you switch the bits around on horizontal level you know the row side will still be ok - balancing the column side with brute force should be easy.

You should get it done by yourself now.

>>3130209
I don't understand what you did.

>>3130232
First I filled every row from the start and calculated unbalances for columns.

If the unbalances do not add up to 0 it is unsolvable. If they add up to zero you can start with columns, that have negative number. you can horizontally shift a filled square from ANY column with positive number into ANY empty square with negative number (and then you adjust the numbers accordingly). Do this until it balances to zero.

Do you get it now?

Sorry about my unclear English - when I am drunk and sleep deprived, then first thing my brain turns off in energy saving mode is foreign language skills.

>>3130244
Well. I understood it.
Guess OP understood it too.

>>3130256
Nope.. will not work. While you can shift boxes between columns, you dont know which row to switch in.

>>3130271
Maybe adding. "If in a row, there is column where current total is positive and different column where total is negative, then in this row, fill negative column and remove positive column."

>>3130244
>>3130244
>you can horizontally shift a filled square from ANY column with positive number into ANY empty square with negative number
How do you know which colums contain a +ve or -ve number?

>>3130271
you take any qualifying row ... it won't generate a dead end or cyclic movement

>>3130284
you count it and keep updating it ... doh

>>3130311
dun geddit.

>>3130325
Do you not get the algorithm or do you not get why it would work?

>>3130328
I don't understand the algorithm.

>>3130345
Ok, we start up with the source - I'll take one from your exampel
.52325
5
2
3
2
5

The we fill it with 'x'-s from the start so that every row has a number of 'x'-s required. We will count the number of surplus/missing 'x'-s by column

xxxxx
xx
xxx
xx
xxxxx

Now the rows are OK and if we only shift the 'x'-s horizontally they will always be ok. We count what is wrong with columns where positive numbers are extra x-s and negatives are missing x-s.

0,3,0,0,-3

Now we add all these together and if it is not 0 we declare unsolvable and exit.

So now we take the first column with negative number. We will find a row where this column does not have an x and any column with positive number has an x and shift this x, then increase the negative number and decrease the positive number. Do this until all the column numbers are 0.

Just code it and you will see it works.

fuck this thread and everyone in it

>>3130369
Holy fucking shit, son. Over 9000 Internets to you. How did you figure it out?

>>3130479
It just came to me. I'm a former genius turned alcoholic, who is trying to turn his life around. Was a nice exercise.

>>3130500
Well good luck turning your life around, brother. Thanks again, anon!

>>3130369