Author Topic: Help with a Brute-force Search?  (Read 3455 times)

Offline Childe

  • DnD Handbook Writer
  • ***
  • Posts: 485
  • Even forever must end, I think. ...
    • View Profile
    • Legend RPG, Rule of Cool Gaming
Help with a Brute-force Search?
« on: February 11, 2012, 08:38:18 PM »
If anyone has the time and is willing to program a brute-force search for the following 6 equations, with the noted constraints, I will give them a cookie or something. I know nothing of programming, or I would do it myself.

Constraint 1: all variables are non-negative integers (0, 1, 2, ...)
Constraint 2: all variables have a minimum of 0 and a maximum of 20.
Constraint 3: L is not 0.

Equations:
4 = (A(BC+D(1+ROUNDDOWN(L/3)))+E)/((F(G(H+I)+J)+(1+ROUNDDOWN(L/3))x(7+ROUNDDOWN(L/3)))-(4+ROUNDDOWN(L/3)))
4 = (A(BC+D(1+ROUNDDOWN(L/3)))+E)/((F(G(H+I)+J)+(1+ROUNDDOWN(L/3))x(4+ROUNDDOWN(L/3)))-(7+ROUNDDOWN(L/3)))
4 = (A(BC+D(4+ROUNDDOWN(L/3)))+E)/((F(G(H+I)+J)+(1+ROUNDDOWN(L/3))x(7+ROUNDDOWN(L/3)))-(1+ROUNDDOWN(L/3)))
4 = (A(BC+D(4+ROUNDDOWN(L/3)))+E)/((F(G(H+I)+J)+(1+ROUNDDOWN(L/3))x(1+ROUNDDOWN(L/3)))-(7+ROUNDDOWN(L/3)))
4 = (A(BC+D(7+ROUNDDOWN(L/3)))+E)/((F(G(H+I)+J)+(1+ROUNDDOWN(L/3))x(4+ROUNDDOWN(L/3)))-(1+ROUNDDOWN(L/3)))
4 = (A(BC+D(7+ROUNDDOWN(L/3)))+E)/((F(G(H+I)+J)+(1+ROUNDDOWN(L/3))x(1+ROUNDDOWN(L/3)))-(4+ROUNDDOWN(L/3)))

I'm looking for all valid solutions. There are 120(21^10) configurations, which are just a few too many for me to try myself...
"You had a tough day at the office. So you come home, make
yourself some dinner, smother your kids, pop in a movie, maybe
have a drink. It's fun, right? Wrong. Don't smother your kids."
- The More You Know

Offline sirpercival

  • Epic Member
  • ****
  • Posts: 10855
  • you can't escape the miles
    • View Profile
Re: Help with a Brute-force Search?
« Reply #1 on: February 11, 2012, 09:21:30 PM »
Sure, I can do this.  Chill for a few.

EDIT: L is 1 to 20?  And there's no K?
« Last Edit: February 11, 2012, 09:23:59 PM by sirpercival »
I am the assassin of productivity

(member in good standing of the troll-feeders guild)

It's begun — my things have overgrown the previous sig.

Offline Childe

  • DnD Handbook Writer
  • ***
  • Posts: 485
  • Even forever must end, I think. ...
    • View Profile
    • Legend RPG, Rule of Cool Gaming
Re: Help with a Brute-force Search?
« Reply #2 on: February 11, 2012, 09:30:04 PM »
Correct on both. I named L before I realized there wasn't actually going to be a K.

Thank you very much.
"You had a tough day at the office. So you come home, make
yourself some dinner, smother your kids, pop in a movie, maybe
have a drink. It's fun, right? Wrong. Don't smother your kids."
- The More You Know

Offline sirpercival

  • Epic Member
  • ****
  • Posts: 10855
  • you can't escape the miles
    • View Profile
Re: Help with a Brute-force Search?
« Reply #3 on: February 11, 2012, 09:41:16 PM »
Hey man, I'm sorry -- I was going to do this in IDL (which is the only language I really know), but it's gonna be WAY too slow to do something like this in IDL.  It should really be in C or Fortran.  Sorry :(
I am the assassin of productivity

(member in good standing of the troll-feeders guild)

It's begun — my things have overgrown the previous sig.

Offline X-Codes

  • DnD Handbook Writer
  • ****
  • Posts: 2001
  • White, Fuzzy, Sniper Rifle.
    • View Profile
Re: Help with a Brute-force Search?
« Reply #4 on: February 11, 2012, 10:52:11 PM »
Strictly left to right, correct (well, except for parenthesis)?

EDIT: Nevermind, it's too many stunts to pull to make it look linear...
« Last Edit: February 11, 2012, 11:04:46 PM by X-Codes »

Offline Childe

  • DnD Handbook Writer
  • ***
  • Posts: 485
  • Even forever must end, I think. ...
    • View Profile
    • Legend RPG, Rule of Cool Gaming
Re: Help with a Brute-force Search?
« Reply #5 on: February 11, 2012, 11:00:17 PM »
I'm not sure what you're asking.

Standard order of operations, looking for all variable combinations within the defined range that are valid solutions for the whole equation (for each equation).
"You had a tough day at the office. So you come home, make
yourself some dinner, smother your kids, pop in a movie, maybe
have a drink. It's fun, right? Wrong. Don't smother your kids."
- The More You Know

Offline X-Codes

  • DnD Handbook Writer
  • ****
  • Posts: 2001
  • White, Fuzzy, Sniper Rifle.
    • View Profile
Re: Help with a Brute-force Search?
« Reply #6 on: February 11, 2012, 11:06:26 PM »
Oh, I see.  Those multiplication functions are inside another set of parenthesis after those division functions.  That DOES make my question moot.

Offline X-Codes

  • DnD Handbook Writer
  • ****
  • Posts: 2001
  • White, Fuzzy, Sniper Rifle.
    • View Profile
Re: Help with a Brute-force Search?
« Reply #7 on: February 11, 2012, 11:29:39 PM »
Let K be an integer between 0 and 6 such that K = ROUNDDOWN(L/3).

4 = (ABC+1AD+ADK+E)/(FGH+FGI+FJ+7+8K+K^2-4-K)
4 = (ABC+1AD+ADK+E)/(FGH+FGI+FJ+4+5K+K^2-7-K)
4 = (ABC+4AD+ADK+E)/(FGH+FGI+FJ+7+8K+K^2-1-K)
4 = (ABC+4AD+ADK+E)/(FGH+FGI+FJ+1+2K+K^2-7-K)
4 = (ABC+7AD+ADK+E)/(FGH+FGI+FJ+4+5K+K^2-1-K)
4 = (ABC+7AD+ADK+E)/(FGH+FGI+FJ+1+2K+K^2-4-K)

4 = (ABC+1AD+ADK+E)/(FGH+FGI+FJ+3+7K+K^2)
4 = (ABC+1AD+ADK+E)/(FGH+FGI+FJ-3+4K+K^2)
4 = (ABC+4AD+ADK+E)/(FGH+FGI+FJ+6+7K+K^2)
4 = (ABC+4AD+ADK+E)/(FGH+FGI+FJ-6+1K+K^2)
4 = (ABC+7AD+ADK+E)/(FGH+FGI+FJ+3+4K+K^2)
4 = (ABC+7AD+ADK+E)/(FGH+FGI+FJ-3+1K+K^2)

12+28K+4K^2 = ABC + 1AD + ADK + E - 4FGH - 4FGI - 4FJ
-12+16K+4K^2 = ABC + 1AD + ADK + E - 4FGH - 4FGI - 4FJ
24+28K+4K^2 = ABC + 4AD + ADK + E - 4FGH - 4FGI - 4FJ
-24+4K+4K^2 = ABC + 4AD + ADK + E - 4FGH - 4FGI - 4FJ
12+12K+4K^2 = ABC + 7AD + ADK + E - 4FGH - 4FGI - 4FJ
-12+4K+4K^2 = ABC + 7AD + ADK + E - 4FGH - 4FGI - 4FJ

Maybe from here you can break down the whole setup into simpler processes?  It'd probably take me a few days, but I think I could put together a Java algorithm to solve this from here.  At this point, it's basically 7 6x7 matrices (6x8 augmented) for K=0...6.

Offline sirpercival

  • Epic Member
  • ****
  • Posts: 10855
  • you can't escape the miles
    • View Profile
Re: Help with a Brute-force Search?
« Reply #8 on: February 11, 2012, 11:46:37 PM »
Wait, is each one being solved individually?  Or is it solved as a system?  Because if it's the former, that's easy and I can do it tomorrow.  I thought it was a system.
I am the assassin of productivity

(member in good standing of the troll-feeders guild)

It's begun — my things have overgrown the previous sig.

Offline X-Codes

  • DnD Handbook Writer
  • ****
  • Posts: 2001
  • White, Fuzzy, Sniper Rifle.
    • View Profile
Re: Help with a Brute-force Search?
« Reply #9 on: February 11, 2012, 11:53:17 PM »
I guess my method would be harder to program... but it'd be a more efficient program. lol

I'd use nested for loops for each of the variables, and then use an if statement to check each equation.  If they're all true, print some numeric output.  Else, just move on to the next set.

EDIT: That's about 1.22*10^15 calculations, I think.  I suppose that's an overestimate, since it will terminate as soon as it hits one that's false.

EDIT 2: I think I'm a little silly from sleep deprivation.
« Last Edit: February 11, 2012, 11:56:17 PM by X-Codes »

Offline Childe

  • DnD Handbook Writer
  • ***
  • Posts: 485
  • Even forever must end, I think. ...
    • View Profile
    • Legend RPG, Rule of Cool Gaming
Re: Help with a Brute-force Search?
« Reply #10 on: February 11, 2012, 11:58:31 PM »
Good question, sirpercival! I can't believe I didn't clarify that -- they're being solved as a system! So I'm looking for values for the variables that satisfy all 6 equations simultaneously.

Also, ideally, I'm looking for variable combinations for A-J that support as many of the L possibilities, but that's really optional for this, I guess.
"You had a tough day at the office. So you come home, make
yourself some dinner, smother your kids, pop in a movie, maybe
have a drink. It's fun, right? Wrong. Don't smother your kids."
- The More You Know

Offline Agita

  • He Who Lurks
  • Moderator
  • *****
  • Posts: 2705
  • *stare*
    • View Profile
Re: Help with a Brute-force Search?
« Reply #11 on: February 12, 2012, 07:19:06 AM »
I've done some Fortran before (read: took one class and wrote a few programs for that class), but the extent of my programming skill would be to literally just run all the variables from 0 to 20 one by one and check each equation separately (terminating as soon as one equation is not fulfilled, of course); I don't have the know-how to do anything that's faster.
Please send private messages regarding board matters to Forum Staff instead.