• We are delighted to introduce GiftBot 2.0, the next generation of our popular gifting feature. To celebrate, we'll be giving away some incredible prizes over the coming weeks in one big Giveaway Extravaganza!

Programming |OT| Functional, Imperative, OOP, Cargo-Cult,... all are welcome!

MotiD

Member
Oct 26, 2017
786
Can anyone help me in private with a recursive method that uses a backtracking algorithm I’m writing in Java? I can’t quite put my finger on why it doesn’t work properly and going over a recursive function with a debugger can be confusing and it didn’t really help
 

Gimdrek

Member
Oct 27, 2017
22
I am having some issues with learning to code in Lua. I bought the book "Beginning Lua Programming" by Kurt Jung and Aaron Brown, and I am having problems remembering the code I read earlier. So how do you remember this stuff? Is it just repetition and muscle memory when you deal with coding? Do you need to remember everything? FYI I wanted to learn an easy programming language and thought this would be great since I play "World of Warcraft". I can make my own addons and what not, which got me excited.

I guess I need to learn how to read,study and concentrate better :/
 

BreakyBoy

Member
Oct 27, 2017
163
I am having some issues with learning to code in Lua. I bought the book "Beginning Lua Programming" by Kurt Jung and Aaron Brown, and I am having problems remembering the code I read earlier. So how do you remember this stuff? Is it just repetition and muscle memory when you deal with coding? Do you need to remember everything? FYI I wanted to learn an easy programming language and thought this would be great since I play "World of Warcraft". I can make my own addons and what not, which got me excited.

I guess I need to learn how to read,study and concentrate better :/
Like any skill, repetition/practice does help immensely.

That being said, you really don't need to memorize a lot. It sounds like you're just getting started, so I imagine you might be stuck a bit on the idea if this as a new "language" where a big part of being "fluent" is having a large vocabulary/grammar rules in your head that you can just recall effortlessly to communicate.

That's not really how programming works. Having a ready command of the syntax and functions is certainly immensely helpful, but what is vastly more important is to understand fundamental principles and patterns that are common to most programming projects regardless of the languages or frameworks you might be using.

Plenty of skilled, professional developers are near useless without an IDE or a some sort of reference material to help them piece together the project they are working on.

Lua is a fine choice to start with, and having a project you're excited about like a World of Warcraft add-on is invaluable to keep you going when you feel stuck (and you will, we all have, and often still do).

Just keep at it. Keep trying to build things. Ask questions. It'll come together, it just takes time and practice. If you forget something you read, or aren't sure you got it straight the first time, go back and read it again. Try to take the concept and implement it in a tiny program of your own. It doesn't have to be a complex thing. Just focus on trying to implement/demonstrate the thing you're trying to learn.
 

GyrosOfWar

Member
Oct 25, 2017
83
Vienna
I am having some issues with learning to code in Lua. I bought the book "Beginning Lua Programming" by Kurt Jung and Aaron Brown, and I am having problems remembering the code I read earlier. So how do you remember this stuff? Is it just repetition and muscle memory when you deal with coding? Do you need to remember everything? FYI I wanted to learn an easy programming language and thought this would be great since I play "World of Warcraft". I can make my own addons and what not, which got me excited.

I guess I need to learn how to read,study and concentrate better :/
The first thing to note is that programmers look stuff up all the time. You'll remember the stuff you use all the time (Syntax, basic library functions) but there's lots of stuff that you won't remember and that's fine. Google, Stack Overflow and the language docs are your best friend. I would actually say that a not-so-small part of being a productive programmer is knowing how to use a search engine to find good results that will help you.

Also, you won't remember code as in, "I'll remember this snippet of code that solves this specific problem". Over time, you learn patterns that solve certain types of problems and that pattern will be what you remember.
 

Gimdrek

Member
Oct 27, 2017
22
ok great thanks for the help! sounds like I have been approaching this the wrong way. I just need to read, then build example code to understand the chapters better, then move on.
 

MotiD

Member
Oct 26, 2017
786
if I have two completely separate for loops used twice in a Java class and both times running from i=0 through n

for(int i =0; i<n; i++)

Is the time complexity O(n) (actually 2n) or O(n^2)?
 

Kieli

Member
Oct 28, 2017
1,954
if I have two completely separate for loops used twice in a Java class and both times running from i=0 through n

for(int i =0; i<n; i++)

Is the time complexity O(n) (actually 2n) or O(n^2)?
If they are not nested, the algorithm is as slow as the slowest step. If it is nested, then it is multiplicative.
 

Cyborg009

Member
Oct 28, 2017
308
Has anyone here used cefsharp? I having issues closing my current tabbed browser. browser.Dispose() just kills my entire process.
 

GaimeGuy

Member
Oct 25, 2017
4,320
if I have two completely separate for loops used twice in a Java class and both times running from i=0 through n

for(int i =0; i<n; i++)

Is the time complexity O(n) (actually 2n) or O(n^2)?
Two completely separate loops back to back or nested?
for(int i =0; i<n; i++)
{
blah;
}
for(int i =0; i<n; i++)
{
blah;
}

Here, we perform "blah" n times.
Then we perform "blah" n times.

It's clearly O(n) since blah runs 2n times.

Now, if it's nested?
for(int i =0; i<n; i++)
{
for(int j=0; j<n; j++)
{
foo;
}
}


We run "foo" n × n times. That's N^2.

It's multiplicative.

Consider N=3. You run foo 9 times, but blah 6 times


In the below example, it's O(n×m)
for(int i =0; i<n; i++)
{
for(int j=0; j<m; j++)
{
bar;
}
}
 
Last edited:

Cyborg009

Member
Oct 28, 2017
308
Probably not, if there's legacy code your stuck with cefsharp is still your best option. Electron would mostly be to build a new desktop app with browser capability.
Hmm interesting the current application just runs sql querys(Mssql) and displays the data as well as loads some data from a csv file. That shouldn't take too long to recreate . Though I haven't really learn much javascript at all yet.
 

Somnid

Member
Oct 25, 2017
2,425
Hmm interesting the current application just runs sql querys(Mssql) and displays the data as well as loads some data from a csv file. That shouldn't take too long to recreate . Though I haven't really learn much javascript at all yet.
So there's a couple ways you can approach this. I'd start out with looking at making the DB queries into a service, interface with it in term of REST (or GraphQL if you are so inclined). This is going to be a better long term solution as you can decouple whatever application hits the DB from the DB itself. If you move the hardest part probably won't be learning js (though expect to face palm you code in a few years because best-practice isn't quite what you're use to) but rather figuring out how to do a lot of the things .NET just hides from you behind an API. Anyway, like I said the ideal for the client is a PWA because its literally a web app that you can install, you may choose not to do that because you have to get into hosting and permissions, intranet routing and all those things that are easier to just hide in an application (this isn't good practice per-se but it gets the job done). Electron can at least let you locally host things if you just want to hand out the installer and it has more APIs for doing filesystem and IO at the cost of being less secure (because it's a desktop app you install). Also, for actual construction of an app, if you do like working in .NET more you can checkout Blazor: https://dotnet.microsoft.com/apps/aspnet/web-apps/client. In a public web sense there are tradeoffs here I'd be hesitant to make choosing Blazor (payload size) but for an intranet app it could totally work. If you use the hosted model you might even be able to reuse a lot of code.
 

Megasoum

Member
Oct 25, 2017
12,803
Decided to play around and create a simple WPF app in VS 2019 while on vacation and was wondering... Is there some kind of convention or informations anywhere about the design standards? For example, what's the standard height of a text box, how many pixels should I use for margins, etc etc

I looked around a bit on Google but couldn't find anything definitive.
 

quickly

Member
Mar 8, 2018
936
if I have two completely separate for loops used twice in a Java class and both times running from i=0 through n

for(int i =0; i<n; i++)

Is the time complexity O(n) (actually 2n) or O(n^2)?
If the loops are separate the time complexity is O(n), since O(n) + O(n) = O(2n) = O(n). I.e., if you run a linear loop twice, the time complexity is linear. If the loops are nested then the time complexity is O(n) * O(n) = O(n * n), since the inner loop runs for each iteration of the outer loop. The opening chapters of CLRS have a good discussion of time complexity, for what it's worth.
 

quickly

Member
Mar 8, 2018
936
What virtual environment am I supposed to use with modern Python development? venv? virtualenv? other packages? I am not sure.
 

MotiD

Member
Oct 26, 2017
786
If they are not nested, the algorithm is as slow as the slowest step. If it is nested, then it is multiplicative.
Two completely separate loops back to back or nested?
for(int i =0; i<n; i++)
{
blah;
}
for(int i =0; i<n; i++)
{
blah;
}

Here, we perform "blah" n times.
Then we perform "blah" n times.

It's clearly O(n) since blah runs 2n times.

Now, if it's nested?
for(int i =0; i<n; i++)
{
for(int j=0; j<n; j++)
{
foo;
}
}


We run "foo" n × n times. That's N^2.

It's multiplicative.

Consider N=3. You run foo 9 times, but blah 6 times


In the below example, it's O(n×m)
for(int i =0; i<n; i++)
{
for(int j=0; j<m; j++)
{
bar;
}
}
If the loops are separate the time complexity is O(n), since O(n) + O(n) = O(2n) = O(n). I.e., if you run a linear loop twice, the time complexity is linear. If the loops are nested then the time complexity is O(n) * O(n) = O(n * n), since the inner loop runs for each iteration of the outer loop. The opening chapters of CLRS have a good discussion of time complexity, for what it's worth.
Forget to reply. Thank you!
 

spootime

The Fallen
Oct 27, 2017
1,229
I'm starting a fun little side project and I was wondering if anyone had some advice.

My goal is to build a small webapp that will generate a word document based on an uploaded PDF. The PDF is scanned text so I'll need to use OCR. I know that python has tesseract open source libraries and that google offers an OCR API that is apparently pretty good as well. If anyone has any suggestions for what to use on this end let me know.

Anyway, my ultimate goal is to parse through the recognized text of the PDF and fill in fields in a word template. Is this feasible? I'm most concerned about the OCR part - filling in the fields should be trivial based on what I've looked at so far. I've read a lot of nightmare stories about OCR recognizing individual characters instead of words, making it impossible to parse.
 

MotiD

Member
Oct 26, 2017
786
I'm banging my head against this problem with recursion for some time now and I still haven't been able to solve it, even tho I've got the basic idea down but I keep failing on execution

I need to write a *recursive* boolean method that checks if a given number can be written as the sum of powers of three
so, for example 37 will return true because 3^0 + 3^2 + 3^3 = 37
38 will return false

I can't use any loops or any libraries, just the Math library
My basic idea is to use backtracking and subtract from the number I've been given, if num < 0 then I return false and being backtracking accordingly and check a larger power and so on
 

Zevenberge

Member
Oct 27, 2017
351
I'm banging my head against this problem with recursion for some time now and I still haven't been able to solve it, even tho I've got the basic idea down but I keep failing on execution

I need to write a *recursive* boolean method that checks if a given number can be written as the sum of powers of three
so, for example 37 will return true because 3^0 + 3^2 + 3^3 = 37
38 will return false

I can't use any loops or any libraries, just the Math library
My basic idea is to use backtracking and subtract from the number I've been given, if num < 0 then I return false and being backtracking accordingly and check a larger power and so on
Can you have doubles? I.e.

2 * 3^1 + 3^2 = 15

I assume you can't, because otherwise the implementation would be `return true;`. (Any integer is a sum of 1.)

You can prove it formally, but how do (3^0 + 3^1) and (3^2) relate? How do (3^0 + 3^1 + 3^2) and 3^3 relate?

Every higher power is larger than the sum of the smaller powers.

Given this, how can we use recursion to solve this problem? Recursion solves a part of the puzzle and uses the same solver to solve the rest. Preferably we use the previous answer to prevent backtracking.

Instead of going up, we go down. We don't need to back track, because our answer is always deterministic.
 

Post Reply

Member
Aug 1, 2018
1,934
I'm banging my head against this problem with recursion for some time now and I still haven't been able to solve it, even tho I've got the basic idea down but I keep failing on execution

I need to write a *recursive* boolean method that checks if a given number can be written as the sum of powers of three
so, for example 37 will return true because 3^0 + 3^2 + 3^3 = 37
38 will return false

I can't use any loops or any libraries, just the Math library
My basic idea is to use backtracking and subtract from the number I've been given, if num < 0 then I return false and being backtracking accordingly and check a larger power and so on
Is your example right? 3^1 is missing, so the case of '37' should actually be false too if I understand the problem right

Also, if you think about this problem, you actually have 2 cases that you can use as base cases. If you go that route, you don't have to backtrack and can just keep recursing until you hit one of those 2 cases.

Edit: I think I misread your problem. I think you're not dealing with a series, but are instead just looking to see if the sum of any combination of powers of 3 will equal some number?
 
Last edited:

Klappdrachen

Member
Oct 26, 2017
829
I realize that this is not really a programming question but I think this is the best place to ask anyway: Can anybody recommend books, tutorials, YouTube channels etc. on first year computer architecture topics? Namely stuff like interrupts, subroutines, ISA, pipelining, cache coherence... The learning material that I got as part of the lecture is completely useless and I couldn't find anything decent online as of yet.
 

metaprogram

Member
Oct 28, 2017
965
I'm banging my head against this problem with recursion for some time now and I still haven't been able to solve it, even tho I've got the basic idea down but I keep failing on execution

I need to write a *recursive* boolean method that checks if a given number can be written as the sum of powers of three
so, for example 37 will return true because 3^0 + 3^2 + 3^3 = 37
38 will return false

I can't use any loops or any libraries, just the Math library
My basic idea is to use backtracking and subtract from the number I've been given, if num < 0 then I return false and being backtracking accordingly and check a larger power and so on
This one is easy.

Code:
bool is_sum_of_powers_of_three(unsigned N) {
  return true;
}
x = 3^0 + 3^0 + ... + 3^0 (x times)

(you never said they had to be different powers of three) :D
 
Last edited:

Kopite

Member
Oct 28, 2017
1,323
I have a simple puzzle, one I've solved a year or so back but can't remember the conditions I need to complete it. Scenario:

You need to write pseudocode to schedule shifts for 2 employees, A and B, for 2 weeks time.
-Constraints
1 - A likes to work on odd dates (such 1st of January, 3rd January)
2 - B likes to work on even dates (2nd, 4th so on)
3 - A dislikes to work on Thursday
4 - B must work on Friday
5 - No one can work continuously for more than 2 days

From the above conditions, we can surmise B must work on Thursday and Friday, so I've written my pseudocode as follows:

Code:
if (Date.getDay = Thursday OR Date.getDay = Friday)

     B works

else if (Date.getDate() MOD 2 = 0) // even date

    B works

else

    A works
The problem is, what if Saturday happens to be an even date, then B would end up working more than 2 days in a row and violate the constraints. What if conditions am I missing? I'm pretty sure it can be done with a Date.getLastDateOfMonth() or Date.getFirstDateOfMonth()

This is the first time I've asked something like this so if I could be clearer, use better syntax feel free to let me know :)
 

metaprogram

Member
Oct 28, 2017
965
Ok now that I'm done with my troll answer, here's my real answer.

Think about this a different way. If a number is a sum of powers of three, does that tell you anything about the number itself? Yes! It tells you that it must be equal to 0 or 1 mod 3. For example, 37 = 3^0 + 3^2 + 3^3, this is equal to 1 mod 3. 36 = 3^2 + 3^3, this is equal to 0 mod 3. Either it's a sum of non-zero powers of 3 (which gives mod 0) or it's a sum of non-zero powers of 3 plus 3^0 (which gives 1 mod 3).

In other words, if the number is equal to 2 mod 3, then it fails instantly!

Secondly, we know that 0 cannot be written as a sum of powers of 3.

And finally, we know that 1 can (3^0).

So already we have three base cases:

Code:
bool check(int n)
{
    if (n == 0)
        return false;
    if (n == 1)
        return true;

    int r = n % 3;
    if (r == 2)
        return false;

    // what goes here?
}
Now what? Well if it's equal to 1 mod 3, then we have the first case. Subtract 1 and try again:

Code:
bool check(int n)
{
    if (n == 0)
        return false;
    if (n == 1)
        return true;

    int r = n % 3;
    if (r == 2)
        return false;

    if (r == 1)
        return check(n - 1);

    // What goes here?
}
If it's equal to 0 mod 3, then we can write it as product of 3 and some other sum of powers of 3. Example:

36 = 3*(3^1 + 3^2)

So just divide by 3 and try again:

Code:
bool check(int n)
{
    if (n == 0)
        return false;
    if (n == 1)
        return true;

    int r = n % 3;
    if (r == 2)
        return false;

    if (r == 1)
        return check(n - 1);

    return check(n / 3);
}
What next? There is nothing next! That's it. Eventually this process will either yield 1 (success) or 2 (failure).
 
Last edited:

phisheep

Member
Oct 26, 2017
743
I have a simple puzzle, one I've solved a year or so back but can't remember the conditions I need to complete it. Scenario:

You need to write pseudocode to schedule shifts for 2 employees, A and B, for 2 weeks time.
-Constraints
1 - A likes to work on odd dates (such 1st of January, 3rd January)
2 - B likes to work on even dates (2nd, 4th so on)
3 - A dislikes to work on Thursday
4 - B must work on Friday
5 - No one can work continuously for more than 2 days

From the above conditions, we can surmise B must work on Thursday and Friday, so I've written my pseudocode as follows:

Code:
if (Date.getDay = Thursday OR Date.getDay = Friday)

     B works

else if (Date.getDate() MOD 2 = 0) // even date

    B works

else

    A works
The problem is, what if Saturday happens to be an even date, then B would end up working more than 2 days in a row and violate the constraints. What if conditions am I missing? I'm pretty sure it can be done with a Date.getLastDateOfMonth() or Date.getFirstDateOfMonth()

This is the first time I've asked something like this so if I could be clearer, use better syntax feel free to let me know :)
It is not possible to satisfy all these constraints in all circumstances. Look at 1 and 3 - A likes to work odd dates, but dislikes working Thursdays. So what happens on Thursday 27th June - does A want to work or doesn't he? Either way you have broken something.

So there's something wrong here with either the constraints you have given, or the objective to be achieved. Conditions 4 and 5 seem absolute ones, but maybe your aim is to maximise likes or minimise dislikes rather than keep A and B happy all the time?
 

Kopite

Member
Oct 28, 2017
1,323
It is not possible to satisfy all these constraints in all circumstances. Look at 1 and 3 - A likes to work odd dates, but dislikes working Thursdays. So what happens on Thursday 27th June - does A want to work or doesn't he? Either way you have broken something.

So there's something wrong here with either the constraints you have given, or the objective to be achieved. Conditions 4 and 5 seem absolute ones, but maybe your aim is to maximise likes or minimise dislikes rather than keep A and B happy all the time?
Yeah the aim is to maximise happiness with only the 4th and 5th being hard constraints. With my code right now though I'll end up violating the 5th (hard)constraint
 

phisheep

Member
Oct 26, 2017
743
Yeah the aim is to maximise happiness with only the 4th and 5th being hard constraints. With my code right now though I'll end up violating the 5th (hard)constraint
I think your problem is you are treating the third (soft) constraint as if it were a hard one.

I'd probably start like this:
- allocate all even days to B and all odd days to A (that gives no three-day runs, and only two-day runs for A on some month ends)
- swap A out and B in for any Fridays A is working (that'll nearly (?) always give a three-day run for B)
- where there's a three day run the middle day is always a Friday, so swap in A for B on the Saturday, unless that makes a three-day run for A (because of month ends) in which case swap the Thursday instead and make A suffer - it's for the greater good.
 

Sectorseven

Member
Oct 25, 2017
3,176
Is anyone familiar with General Assembly boot camps? My state offers a scholarship for their software engineering immersive course and I'm wondering if it's worth doing.
 
Oct 27, 2017
6,637
Anyone know SQL?

I’m studying it right now and I’m at cardinality but it’s a bit confusing and not sticking, I can’t find any real world examples to wrap my head around it. Specifically 0 or 1, 0 or more, and 1 or more.
 

sNtd

Member
Oct 24, 2018
226
Anyone know SQL?

I’m studying it right now and I’m at cardinality but it’s a bit confusing and not sticking, I can’t find any real world examples to wrap my head around it. Specifically 0 or 1, 0 or more, and 1 or more.
Cardinalities are quite arbitrary rules. It's actually pretty hard to come up with clear-cut examples from the natural world. Also the level of support differs per RDBMS. NoSQL databases in particular often forgo cardinalities as a means to simplify design and computation.

0 or 1 (0...1): A either has or has no B, but there is no way to have multiple B's. Can be implemented as a nullable field with a foreign key. A car has either an engine or it has no engine (perhaps the car is still being constructed or is being deconstructed).

0 or more (0...*): A could have a B, it could have multiple B's, it could have no B. Can be implemented by adding a join table (table having the primary keys of two tables). A customer might have a credit card assigned to their account, or the customer might have multiple credit cards, or the customer might have zero credit cards.

1 or more (1...*): A needs to have at least B, but it can have more. Can be implemented by a join table, but you cannot easily guarantee this constraint within the database itself. A customer needs to have at least one bank account.
 
Oct 27, 2017
6,637
Cardinalities are quite arbitrary rules. It's actually pretty hard to come up with clear-cut examples from the natural world. Also the level of support differs per RDBMS. NoSQL databases in particular often forgo cardinalities as a means to simplify design and computation.

0 or 1 (0...1): A either has or has no B, but there is no way to have multiple B's. Can be implemented as a nullable field with a foreign key. A car has either an engine or it has no engine (perhaps the car is still being constructed or is being deconstructed).

0 or more (0...*): A could have a B, it could have multiple B's, it could have no B. Can be implemented by adding a join table (table having the primary keys of two tables). A customer might have a credit card assigned to their account, or the customer might have multiple credit cards, or the customer might have zero credit cards.

1 or more (1...*): A needs to have at least B, but it can have more. Can be implemented by a join table, but you cannot easily guarantee this constraint within the database itself. A customer needs to have at least one bank account.
Thanks, that helps.
 

MotiD

Member
Oct 26, 2017
786
Can you have doubles? I.e.

2 * 3^1 + 3^2 = 15

I assume you can't, because otherwise the implementation would be `return true;`. (Any integer is a sum of 1.)

You can prove it formally, but how do (3^0 + 3^1) and (3^2) relate? How do (3^0 + 3^1 + 3^2) and 3^3 relate?

Every higher power is larger than the sum of the smaller powers.

Given this, how can we use recursion to solve this problem? Recursion solves a part of the puzzle and uses the same solver to solve the rest. Preferably we use the previous answer to prevent backtracking.

Instead of going up, we go down. We don't need to back track, because our answer is always deterministic.
Is your example right? 3^1 is missing, so the case of '37' should actually be false too if I understand the problem right

Also, if you think about this problem, you actually have 2 cases that you can use as base cases. If you go that route, you don't have to backtrack and can just keep recursing until you hit one of those 2 cases.

Edit: I think I misread your problem. I think you're not dealing with a series, but are instead just looking to see if the sum of any combination of powers of 3 will equal some number?
Ok now that I'm done with my troll answer, here's my real answer.

Think about this a different way. If a number is a sum of powers of three, does that tell you anything about the number itself? Yes! It tells you that it must be equal to 0 or 1 mod 3. For example, 37 = 3^0 + 3^2 + 3^3, this is equal to 1 mod 3. 36 = 3^2 + 3^3, this is equal to 0 mod 3. Either it's a sum of non-zero powers of 3 (which gives mod 0) or it's a sum of non-zero powers of 3 plus 3^0 (which gives 1 mod 3).

In other words, if the number is equal to 2 mod 3, then it fails instantly!

Secondly, we know that 0 cannot be written as a sum of powers of 3.

And finally, we know that 1 can (3^0).

So already we have three base cases:

Code:
bool check(int n)
{
    if (n == 0)
        return false;
    if (n == 1)
        return true;

    int r = n % 3;
    if (r == 2)
        return false;

    // what goes here?
}
Now what? Well if it's equal to 1 mod 3, then we have the first case. Subtract 1 and try again:

Code:
bool check(int n)
{
    if (n == 0)
        return false;
    if (n == 1)
        return true;

    int r = n % 3;
    if (r == 2)
        return false;

    if (r == 1)
        return check(n - 1);

    // What goes here?
}
If it's equal to 0 mod 3, then we can write it as product of 3 and some other sum of powers of 3. Example:

36 = 3*(3^1 + 3^2)

So just divide by 3 and try again:

Code:
bool check(int n)
{
    if (n == 0)
        return false;
    if (n == 1)
        return true;

    int r = n % 3;
    if (r == 2)
        return false;

    if (r == 1)
        return check(n - 1);

    return check(n / 3);
}
What next? There is nothing next! That's it. Eventually this process will either yield 1 (success) or 2 (failure).
Hey, thanks for all the answers

Indeed, there can be no repeats of the same power.
I liked the solution using Math properties, but usually the exam strictly forbids using those to reach a solution.

I was still struggling with this until today when someone sent his solution, and it gave me an idea how to restrict the backtracking and end the recursion in case there's no solution (and I'm practicing backtracking because the recursion problem in my upcoming exam has a high chance of being a backtracking problem)

I honestly just wrote this in a minute after getting the idea for the fixed power and still have no idea why this actually works haha
I'm running this on a paper and the debugger to understand why exactly this works

Edit: Alright, here's the code I came up with in a minute without much thought and I expected to iterate upon it, except for some unknown reason it actually works and I have no clue why.
I'm going over it with the debugger and it makes no sense according to the debugger for this to work, but it does

Java:
public class SumPowers3 {

    public static boolean sumPowers3(int num) {

        return sumPowers3(num, 0);
    }

    public static boolean sumPowers3(int num, int power) {
        if(num == 0){
            return true;
        }
        if(Math.pow(3, power) > num){
            return false;
        }
        if(num < 0){
            return false;
        }
        if(sumPowers3(num-(int)Math.pow(3,power), power+1))
        {
            return true;
        }
        return sumPowers3(num, power+1);
    }
    }
Edit 2: I removed the fixedPower variable as I noticed I wasn't even using it. This question sent me on a trip and my head hurts.
 
Last edited:

quickly

Member
Mar 8, 2018
936
I'm going over it with the debugger and it makes no sense according to the debugger for this to work, but it does
Here is another way to think about the problem that emphasizes recursion and backtracking. You are attempting to determine whether there are lists [a_0,...,a_n] of bits such that some number x can be written sum[i=0,n](a_i * 3 ^ i). To the best of my knowledge, this representation is not unique; you might as well solve the more general problem of finding all such lists (your algorithm would terminate when it finds one such list).

Imagine that you wanted to construct all such lists. You have a predicate test(num, bits) that determines whether num is the power sum represented by the coefficients in bits. You know there is a maximum power that determines the maximum list length (and can be computed using logarithms). You know various other things about the boundary conditions of the recursion, so we can focus attention on the recursive case.

In the recursive case, you have a partial solution bits and whatever other pieces of information you are tracking to determine whether to continue searching along the current branch of the recursion tree. If test(num, bits) succeeds, you should perform whatever found action is appropriate and return success (depending on the exact problem, you would either continue searching for solutions or return). If it fails, there are two possibilities to consider.

If no more solutions are possible, you should return failure. If more solutions are possible, you need to consider two cases: in the first case, the next power does not contribute to the sum (i.e., the coefficient is zero); in the second, the next power does contribute to the sum (i.e., the coefficient is one). In either case, you would recursively call your function with the appropriately updated power and solutions, and report whether either recursive call succeeds.

In this explanation, I am constructing solutions and recording them on successful branches of the recursion tree. When a potential solution fails, the algorithm backtracks to the point at which more solutions could be found, and resumes searching from there. There are, of course, many possible optimizations you could make to the algorithm (for example, counting down instead of constructing solutions), but hopefully this helps you understand the structure of the recursion.
 
Last edited:

Quote

Member
Oct 25, 2017
2,293
When is comes to Python and coding in general, i’m making one file scripts and I don’t really know how or when to break up things into more files. Are their any good articles or tutorials on this or what this concept is called? Is it just MVC?
 

metaprogram

Member
Oct 28, 2017
965
Hey, thanks for all the answers

Indeed, there can be no repeats of the same power.
I liked the solution using Math properties, but usually the exam strictly forbids using those to reach a solution.

I was still struggling with this until today when someone sent his solution, and it gave me an idea how to restrict the backtracking and end the recursion in case there's no solution (and I'm practicing backtracking because the recursion problem in my upcoming exam has a high chance of being a backtracking problem)

I honestly just wrote this in a minute after getting the idea for the fixed power and still have no idea why this actually works haha
I'm running this on a paper and the debugger to understand why exactly this works

Edit: Alright, here's the code I came up with in a minute without much thought and I expected to iterate upon it, except for some unknown reason it actually works and I have no clue why.
I'm going over it with the debugger and it makes no sense according to the debugger for this to work, but it does

Java:
public class SumPowers3 {

    public static boolean sumPowers3(int num) {

        return sumPowers3(num, 0);
    }

    public static boolean sumPowers3(int num, int power) {
        if(num == 0){
            return true;
        }
        if(Math.pow(3, power) > num){
            return false;
        }
        if(num < 0){
            return false;
        }
        if(sumPowers3(num-(int)Math.pow(3,power), power+1))
        {
            return true;
        }
        return sumPowers3(num, power+1);
    }
    }
Edit 2: I removed the fixedPower variable as I noticed I wasn't even using it. This question sent me on a trip and my head hurts.
Fwiw, I’m a little confused about the requirement that you can’t arrive at a solution via math.

The answer I gave is still a perfectly acceptable answer. It solves the problem exactly, and the math is just there to explain why it works, much like you would need to use some math to explain why the other answer you posted works.

Sure you can’t use math to avoid using recursion, but it’s still using recursion.
 

sNtd

Member
Oct 24, 2018
226
When is comes to Python and coding in general, i’m making one file scripts and I don’t really know how or when to break up things into more files. Are their any good articles or tutorials on this or what this concept is called? Is it just MVC?
I don't think there is a consensus on which is better in Python, few big files or many small files. Check your framework's or your project/team's guidelines. Also, in Python files are modules and folders with an __init__.py file are packages, so for organization you should try to group strongly related functions into the same files and related files into the same (sub)folder. If you are mainly doing OO programming you could use the Java style of having one file per class, but if the class files are small it might be better to group related classes into the same file.

These days I'm doing a lot of systems programming and I tend to have a few large files, but in the past I used to do more enterprise programming and we would try to have many small files.
 

phisheep

Member
Oct 26, 2017
743
When is comes to Python and coding in general, i’m making one file scripts and I don’t really know how or when to break up things into more files. Are their any good articles or tutorials on this or what this concept is called? Is it just MVC?
This is a tricky thing to get the hang of, and I struggled with it lot - while there seems to be lots of stuff around that tells you how to make Python modules (or the equivalents in other languages), there's not very much to tell you why to do it. I fell back on experimenting and have come up with a few rules of thumb:

1) is there a good reason for splitting things out? My snazzy titactoe implementation (snazzy because it's got useful things like player hints and an undo function and is not only smart enough to win but selectively stupid enough to let the other player win too) has one module for the game engine and another one for the user interface, so it can be run on a text console or a gui.

2) is there a good name for what you are thinking of splitting out? My implementation of Dawkins' Blind Watchmaker evolution thingy has separate modules for "Evolution" and "Development" and another one for the UI. Makes a lot of sense and keeps separate things separate.

3) is there some technical effect you want to achieve? For example, by far the easiest way to do a singleton class in Python is to make it a module rather than a class, because that is exactly how Python modules behave.

4) is the whole thing just too big to understand all at once? If so, try to cleave along fault lines somewhere. My Forth implementation is in four chunks: one for the virtual machine, which is small and has all the tricky logic; one for the builtin functions - there are lots of them, all tiny and mostly unrelated to each other but it is somewhere to put them; one for the bootstrap code, which has to be separate because it is in a different language (Forth rather than C); and one for the memory map which is shared between all of the other three. It's a pragmatic rather than a deeply logical split, and some things - like I/O - are split across different modules depending on how each part is implemented but it does mean that all the machine-dependent stuff whatever it is ends up in the virtual machine module and that's the only bit that needs to change if I port it somewhere else.


The main suggestion though is to experiment. Try mocking the thing up before you have too much code written and see what feels best.
 

Akai

Member
Oct 25, 2017
2,649
Can somebody help me and tell me how I get database files (.db extension) working with Visual Studio 2019, please?

I'm currently working on a ASP.NET project, with the .Net Core 3.0 Preview SDK, and just can't figure out how to use the .db file that's inside the project template, like for reading the data and/or displaying it on a website. I'm actually completely lost and this documentation hasn't really helped me at all.

Would appreciate any help.
 
Last edited:

Zevenberge

Member
Oct 27, 2017
351
Can somebody help me and tell me how I get database files (.db extension) working with Visual Studio 2019, please?
I don't use Visual Studio myself, but this is what I found: https://stackoverflow.com/questions/36407386/what-is-the-vc-db-file-in-visual-studio-projects

I'm currently working on a ASP.NET project, with the .Net Core 3.0 Preview SDK, and just can't figure out how to use the .db file that's inside the project template, like for reading the data and/or displaying it on a website. I'm actually completely lost and this documentation hasn't really helped me at all.

Would appreciate any help.
At a high level, an ASP.NET Core application typically follows the steps:
1. Pick a database framework. EntityFrameworkCore is a good one. You define a class inheriting from DbContext that determines the model you are using and which objects to pull from and save to a database.
2. Register your database accessor class (the DbContext one from step 1) in the Startup class (ConfigureServices method). You supply the connection string to a database service (i.e. SqlExpress). This allows us to look-up the class with the supplied configuration (connection) when we need it.
3. Use constructor injection to get access to the DbContext. In your page/controller, you have a constructor which takes your DbContext as an input parameter. The magic of the AspNetCore framework will then look-up the object you registered in step 2 and pass it on to your page or controller.

It's quite a bit of magic. I've barely scratched the surface, but hopefully you have enough hints to search for further documentation or tutorials.
 

Quote

Member
Oct 25, 2017
2,293
I don't think there is a consensus on which is better in Python, few big files or many small files. Check your framework's or your project/team's guidelines. Also, in Python files are modules and folders with an __init__.py file are packages, so for organization you should try to group strongly related functions into the same files and related files into the same (sub)folder. If you are mainly doing OO programming you could use the Java style of having one file per class, but if the class files are small it might be better to group related classes into the same file.

These days I'm doing a lot of systems programming and I tend to have a few large files, but in the past I used to do more enterprise programming and we would try to have many small files.
This is a tricky thing to get the hang of, and I struggled with it lot - while there seems to be lots of stuff around that tells you how to make Python modules (or the equivalents in other languages), there's not very much to tell you why to do it. I fell back on experimenting and have come up with a few rules of thumb:

1) is there a good reason for splitting things out? My snazzy titactoe implementation (snazzy because it's got useful things like player hints and an undo function and is not only smart enough to win but selectively stupid enough to let the other player win too) has one module for the game engine and another one for the user interface, so it can be run on a text console or a gui.

2) is there a good name for what you are thinking of splitting out? My implementation of Dawkins' Blind Watchmaker evolution thingy has separate modules for "Evolution" and "Development" and another one for the UI. Makes a lot of sense and keeps separate things separate.

3) is there some technical effect you want to achieve? For example, by far the easiest way to do a singleton class in Python is to make it a module rather than a class, because that is exactly how Python modules behave.

4) is the whole thing just too big to understand all at once? If so, try to cleave along fault lines somewhere. My Forth implementation is in four chunks: one for the virtual machine, which is small and has all the tricky logic; one for the builtin functions - there are lots of them, all tiny and mostly unrelated to each other but it is somewhere to put them; one for the bootstrap code, which has to be separate because it is in a different language (Forth rather than C); and one for the memory map which is shared between all of the other three. It's a pragmatic rather than a deeply logical split, and some things - like I/O - are split across different modules depending on how each part is implemented but it does mean that all the machine-dependent stuff whatever it is ends up in the virtual machine module and that's the only bit that needs to change if I port it somewhere else.


The main suggestion though is to experiment. Try mocking the thing up before you have too much code written and see what feels best.
Thank you both. I’ll start to think more about whether it needs to ben split up before I build a thing. That seems like a good place to start.
 

Akai

Member
Oct 25, 2017
2,649
Thanks for the reply, but it seems like I didn't describe my problem properly.

All I wanted was to get this .db file working and I still haven't figured out how. The only success that I had was by converting a copy of the .db file into a .sql file, which when I add it into the project, displays the entire database in a readable state and not in hex code. I think I'll just give up at this point and use the .sql file instead. Wasted way too much time trying to figure it out.

The project is about Emergency Medical Services and the database is filled with relevant information like: Unit #, Unit Type, GPS coordinates (lat/lon/alt), Active, Busy and etc.

My tasks are to:
  • integrate a map (for example Google Maps) on the webpage template (done)
  • list all hospitals and active ambulances/choppers on the webpage table (not done)
  • display markers for every hospital and active ambulances/choppers on the map (not done)
  • have an on-click event for every item in the list, which zooms to the location of the item (not done)
  • (optional) display a pop-up when you click on any marker and display relevant information (not done)
 

Greenpaint

Member
Oct 30, 2017
502
It's good to keep in mind that splitting things off is done for the explicit purpose of making it easier to understand and read for yourself and your fellow human beings. Computers don't care about how many lines of code a file has and splitting won't make your code more efficient (unless splitting also changes execution logic due to architectural changes). Too many small pieces cluttered all over the place can be as hard to read as the Single-File-With-Way-Too-Many-Lines-Of-Code.
 

phisheep

Member
Oct 26, 2017
743
It's good to keep in mind that splitting things off is done for the explicit purpose of making it easier to understand and read for yourself and your fellow human beings. Computers don't care about how many lines of code a file has and splitting won't make your code more efficient (unless splitting also changes execution logic due to architectural changes). Too many small pieces cluttered all over the place can be as hard to read as the Single-File-With-Way-Too-Many-Lines-Of-Code.
Exactly this. My go-to example is the movie Pulp Fiction. If you were to write it as a program you'd have one module for each of the four short stories that make it up, each one in chronological order. It would make a rotten movie, but a far better program.
 

Namorange

The Fallen
Oct 31, 2017
2,735
Exactly this. My go-to example is the movie Pulp Fiction. If you were to write it as a program you'd have one module for each of the four short stories that make it up, each one in chronological order. It would make a rotten movie, but a far better program.
Just to hop onto this. If this were a Java project, you can kind of think of classes as stories. Your stories have a point, a base. Once you start deviating from your original story, you create another story, therefore another class. Sometimes you have to break that convention for convenience, though.
 
Oct 26, 2017
284
I have a question related to design patterns (I'm using C#).

Let's assume that I have the following structure:
Building HAS (one or more) Floor HAS (one or more) Window

Currently each Building contains a list of Floor and each Floor contains a reference to its Building parent. The same logic applies to Window and Floor and their relationship.

I find it cumbersome having to reference the creator in each class constructor (e.g., myBuilding.AddFloor(myBuilding, newFloor))... but I need the children to be explicitly linked to their parent (in both directions... top-down and bottom-up).

Is there a better way of dealing with such a scenario?

Thanks!