Win a copy of Head First Go this week in the Go forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Devaka Cooray
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Tim Holloway
  • Claude Moore
  • Stephan van Hulst
Bartenders:
  • Winston Gutkowski
  • Carey Brown
  • Frits Walraven

Cannot find error in program that repeat a loop  RSS feed

 
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I am stuck with this problem https://open.kattis.com/problems/skener, and I can't find what I am doing wrong.

The problem is basically to scan a character array and repeat row and colons a certain number of times.

My scanned array is correct and the custom test on the page and that I made work. But when I submit I am failing at one test.
What am I doing wrong?




 
Carey Brown
Bartender
Posts: 5654
56
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This
could be replaced with a more readable for() loop
or better yet
Ditto for your rows.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Problem is, I get exactly the same output as I am expecting.
If you look at their sample tests:

Input
3 3 1 2
.x.
x.x
.x.

should give output:
..xx..
xx..xx
..xx..

And input:
3 3 2 1
.x.
x.x
.x.

Should give output:
.x.
.x.
x.x
x.x
.x.
.x.

and this is exactly what I am getting with this program.

But I am failing at a secret test, which means that I miss something.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oups, I forgot:
Do

resets the count when we are done with a colon?
 
Marshal
Posts: 63496
207
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Deja Quavern wrote:Oups, I forgot:
Do

resets the count when we are done with a colon?

I presume by “colon” you mean “column”.
No, you will only reset the counter if you write counter = 0; or similar.
 
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The secret test is probably one that senses performance issues. I suspect your algorithm is taking too long to execute, given you have basically four nested loops.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, my submission was accepted and had a CPU of 0.17 s -- if your submission's CPU is significantly more than that, you'll probably fail that last test that checks for performance.

Edit: I looked at the problem page again and it looks like the threshold for the performance test is 1s so your program must be exceeding that.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here are some hints that might help you find a different way to solve this that performs better:

1. I didn't use a char[][]
2. I only use one System.out.println() statement in the entire program. No System.out.print() statements were used.
3. I only have essentially 3 levels of nesting; you have four.
4. I only zoomed columns when necessary
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not using a char[][] eliminated the need for me to do anything like this:

Eliminating this will probably save you a significant amount of time.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, you could do this instead:

But again, it's really not necessary to use a char[][] to solve this problem.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
From my testing done locally with JUnit, it seems like using Arrays.fill() to zoom columns might also allow you to eke out a few milliseconds of performance for large column zoom values.
 
Ranch Hand
Posts: 90
Java Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:The secret test is probably one that senses performance issues. I suspect your algorithm is taking too long to execute, given you have basically four nested loops.



#OP Junilu is right. The site says that they sometimes provide some additional info

In some cases, we provide extra information apart from the judgement itself, to help you debug your code. This information is available on the page for the respective submission (available by clicking on the corresponding submission ID in your list of submissions)



https://open.kattis.com/help/judgements#tle

This kattis site seems to be cool...
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Thanks for the help but this is wrong.
The performance is fine, the error is definitely in the program, as you can see it runs in 0.09s.



Can you kindly suggest me custom tests instead?
Screenshot-2019-02-22-at-05.10.09.png
[Thumbnail for Screenshot-2019-02-22-at-05.10.09.png]
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For example, when I was solving another problem https://open.kattis.com/problems/stringmatching which is meant to be solved with KPM algorithm and not native methods, I did get a time limit exceeded error. ( I also attach a picture)

This issue is definitely that i am missing an edge case. I already tested one character only, and the input cannot be zero so I can't find what's going on.
Screenshot-2019-02-22-at-05.21.32.png
[Thumbnail for Screenshot-2019-02-22-at-05.21.32.png]
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Not using a char[][] eliminated the need for me to do anything like this:

Eliminating this will probably save you a significant amount of time.



Hi everyone!
I found the issue, it was that my counter uses "row" twice. It passed the first tests because number of rows and colonns are the same

Now I pass with cpu time of 0.08 to 0.30 s.

I am really curious on how Junilu solved without char array, mind to explain?
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is what I submitted:

The processing and output can be done on the fly as input comes in so there's really no need for a temporary storage area for the input. Also, I don't execute the zooming logic for columns unless it's necessary, i.e., the zoom factor for columns, zc, is greater than 1. To zoom row-wise, you simply print the same row zr number of times. Your algorithm goes through the column zooming logic zr number of times whereas I do it one time, at most.

This probably could use some more refactoring to clarify intent but since it's a one-off thing, I thought I had refactored it enough to allow me to test and just keep everything broken down into small enough chunks of work to keep complexity in check.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's a lot to be said about functional decomposition. It only took me less than an hour between first replying, "Yeah, it's probably an issue with performance," and then "Yup, my submission was accepted." That included checking out the legitimacy of that site, registering for an account, validating my email, then submitting my solution. I think it took about 45 minutes actually. And I had unit tests for my code, too.

It's not that I'm super smart or anything but I have a very disciplined problem solving process, namely, Test-Driven Development. The discipline this gives me in systematically attacking a problem is really what helps me go fast. Plus, it forces me to think through a problem in small chunks, building on one small successful experiment after another until I get the final solution.

I actually only did less than 10 Red-Green-Refactor cycles to solve this. With each cycle lasting only 2-3 minutes long, it probably took me 30 minutes max to solve this problem.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I wrote:This is what I submitted


Actually, this is what I submitted:

The first version I gave above was another experiment I did to see if Arrays.fill() performed faster. Based on the results I saw, Arrays.fill() does seem to be slightly faster when using larger zoom factors. Again, this is the beauty of breaking things down into smaller chunks. It was way easier for me to experiment with a different way of zooming columns when I have the logic extracted to its own method. That helps me avoid inadvertently creating bugs because I'm working on a very focused part of the code that's in its own little "compartment".
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:This is what I submitted:


Thank you Junilu for your reply!

Just for those easy problems (1.3 to 1.5), it usually takes me a few minutes, max 15. Performance is never an issue (you need to think about performance when the rating reaches 4)
So they are good to practice as a beginner, to get the flow.

You are really welcome to help me with the problem String Matching:https://open.kattis.com/problems/stringmatching !!
The problem is easy and it's only about performance. (shall I open a new thread for that?)


I like your code, can I ask you more questions?

What is that syntax? Why do you have a new TextEnlarger inside it's own class? What does dot solve mean? Why don't you do it directly?

new TextEnlarger().solve();




What is happening here?
Why the * before zoom? Is it a reference?
Why do we have an offset?
Why do we return the value of buf?

private String zoomColumn(String line, int zoom) {
       char[] buf = new char[line.length() * zoom];
       int offset = 0;
       for (char ch : line.toCharArray()) {
           Arrays.fill(buf, offset, offset + zoom, ch);
           offset += zoom;
       }
       return String.valueOf(buf);
   }

}

 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
arf. My reply is in the quote. Sorry about that. I unquoted but not enough!
 
Marshal
Posts: 24199
54
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fixed that for you.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

max 15 (to solve)


Sure, if you get it right the first time. Very rarely do we programmers get the solution right the first time, do we? Or even the second, third, or fourth time.

For this problem, it took you at least a few hours to find your bug, didn't it? Even with a few people looking at your code, the bug still remained elusive. So, don't just count the time you were at your keyboard, typing away at the code. Count the time you spend thinking about the problem and coming up with a solution, and going out doing research to figure out why your solution isn't working for all cases, and debugging and testing, etc. Count ALL the time it takes you to get from not done to completely done.

 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

What is happening here?

new TextEnlarger().solve()


new TextEnlarger() creates a new TextEnlarger object

.solve() invokes that object's solve() method

It is basically a shortcut for doing this:

Since this would be the only code inside main(), I don't need the temporary problem variable to hold the object reference. I only need the object reference to invoke the solve() method so that's what I do immediately with the newly created object.

Plus, we always say that Main is a Pain, so practice what you preach, right? I prefer to deal with objects and their instance methods rather than with static methods. I can write unit tests the way I'm used to writing them this way. Plus, it allows me to think in a more object-oriented way rather than be constantly pulled back to a procedural mindset.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Why the * before zoom? Is it a reference?


No, that's a multiplication operator.

If you have a string that is N characters long and you need to repeat each character Z number of times, then you're going to end up with a string that is N * Z characters long, right?

So N = line.length and Z = zoom.

So, in order to hold all those characters, I need a char[] that has (line.length * zoom) number of elements in it.

You can use any expression that evaluates to an integer to initialize an array with a specific size. It doesn't always have to be an integer literal.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Why do we have an offset?


You need to know where you are going to start at each iteration. The offset tells you how far away from the beginning of the array your next zoomed character goes.

If you have to zoom ".x." four times, then you'll end up with 12 characters total, right? (".x.". length() * 4)

So, char buf = new char[line.length() * zoom] gives you a char[12] basically.

So for (char ch : line.toCharArray()) -- take each character, ch, in the String line

Arrays.fill(buf, offset, offset + zoom, ch) fill the buf array with repeats of ch starting at index offset and ending at index offset + zoom.

The offset variable is needed to keep track of where the next zoomed character will go.

Why do we return the value of buf?


Because that's the line parameter with all the columns zoomed. That's what the method name says, right? zoomColumn?

We return this value because if we need to zoom rows, we just print this value multiple (zr) times. We don't have to calculate the zoomed columns all over again every time we zoom a row.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Why do we return the value of buf?


If you're asking why we need to return String.valueOf(buf) instead of just buf, then it's because the zoomColumn() method was declared to return a String, not a char[].

String.valueOf(char[]) will return the String equivalent of the specified char array.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I just realized something here: my solution never actually uses the second int in the input, the number of columns. Yet, it was still accepted. Either there's a missing test or the folks on that site assumed that everyone would use a temporary storage area like a char[][] to hold the input data because that's what they did in their solution.

With these kind of programming challenges, invalid input is seldom tested explicitly though so I'm inclined to think that the framers of the problem also had a char[][] in mind as part of their own solution. Also, they had to account for other languages that perhaps did not support jagged arrays. Edit: Actually, the fact that Java uses nested arrays rather than truly multidimensional arrays, and allows for jagged arrays has nothing to do with it. I don't think there's any language they allow where you'd actually need to read all the input data first, then process it.

The only valid reason for giving a "number of columns" value that I can think of is so that you can enforce symmetry of the input data.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:Fixed that for you.



Sorry I missed that!

Thank you Paul, and thank you Junilu for your detailed reply.
I have to ponder over it a while :)
 
Campbell Ritchie
Marshal
Posts: 63496
207
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . Arrays.fill() does seem to be slightly faster . . . .

There is a little pitfall with Arrays#fill(); it uses exactly the same value to fill the entire array, so unless you fill with something like Double.NAN, all elements are the same, i.e. ∀ ij • {ij} ⊆ (0...myArray.length) → myArray[i] == myArray[j] where ... works on a first inclusive last exclusive basis.
And the documentation link shows another pitfall. That method takes Object and Object[] as its parameter types, rather than T and T[], so it is not type‑safe, but might throw an exception if the elements aren't the correct type at runtime..
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:

max 15 (to solve)


Sure, if you get it right the first time. Very rarely do we programmers get the solution right the first time, do we? Or even the second, third, or fourth time.

For this problem, it took you at least a few hours to find your bug, didn't it? Even with a few people looking at your code, the bug still remained elusive. So, don't just count the time you were at your keyboard, typing away at the code. Count the time you spend thinking about the problem and coming up with a solution, and going out doing research to figure out why your solution isn't working for all cases, and debugging and testing, etc. Count ALL the time it takes you to get from not done to completely done.



Please, do not take my words out of context. I said "Just for those easy problems (1.3 to 1.5), it usually takes me a few minutes, max 15." And that means: for those easy problems, it takes me usually a short time from reading the problem description to post a solution, that is accepted. You took just the last words, and changed the whole meaning of what I meant!

Just in that case : the bug was a trivial mistake that I discovered a few hours later (not after a few hours spent on staring at the code, I have lots of other things do at school). You assumed directly it was a performance issue, without looking properly (I don't blame you, it was quite a boring code, but just don't jump on conclusions).

But while grateful for all explanations you posted about your code, I feel slightly patronised and uncomfortable.
 
Junilu Lacar
Sheriff
Posts: 13187
219
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let me clarify: I'm not patronizing you. I was simply trying to make a point. Maybe I didn't word it correctly and some intent was lost in translation. That's the problem with written communication, a lot of tone and intent is lost and it's left up to the reader to fill those gaps with their own imagination. At any rate, if you felt patronized, I apologize; that certainly was not my intent.

In my day job as a technical coach, I teach developers how to write better code, faster. One common problem I see is exactly what I described: that many developers only seem to count the time they are actually at the keyboard typing away as their "development time." Because of this, they fall into all kinds of traps when they try to estimate how much time it will take to complete a task. They end up missing deadlines, missing bugs, and generally getting themselves and others into all kinds of uncomfortable situations. In a discussion I had last week, we actually determined that even the smallest task would take a developer at least 4 hours from starting it to being completely done with it.

These kinds of things happen all the time when you're working out in the real world so you need to find strategies and techniques to deal with it. You seem like a smart student. But what matters most, which I also see from your posts so far, is that you care about your work. That is very important if you're planning to continue down this path and do it professionally later on. As a student, it would be good for you to learn (or better yet, be taught) good engineering habits. I see from your other posts that you're actually writing unit tests. That's very good and perhaps a sign of hope that things might actually be getting better on the academia side. Keep doing that and make a habit of it because it will help you, as it has helped me through the years.

One last tip on becoming a better programmer, one that I wish someone had told me when I was younger: try to practice egoless programming. When you keep the tenets of egoless programming in mind, it dramatically changes how you perceive and receive feedback from other people. So something that might have felt patronizing before would feel less so and more like just some friendly advice, which is what my intent was all along. Maybe I should have just added a a to convey that.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for your kind answer and being considerate of my feelings. And that's true that while reading a reply one can interpret the tone as harsh when it is not.

And of course you are right about underevaluating programming time. I confirm it's a problem and often end up late on math assignments.

I will try to egoless my attitude . I googled the concept a bit, sounds like buddhism.
 
Marshal
Posts: 6595
443
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Deja Quavern wrote:Just in that case : the bug was a trivial mistake that I discovered a few hours later (not after a few hours spent on staring at the code, I have lots of other things do at school).


Technically no difference in it.

An example
Flow: Finished coding 00:00 at midnight (introduced bug in it), figured out about the bug at 02:00 am, solved in 1 minute - luckily trivial mistake.
Result: Problem been unsolved for 2 hours and 1 minute, even though to fix it took only 1 minute. In those 2 hours and 1 minute many things can go wrong.

I'm sure you understand the importance what Junilu mentioned. It isn't just: "ahh, ok, got bug, nevermind, it was trivial to fix".

Deja Quavern wrote:I will try to egoless my attitude


That's not an easy task, I can assure you

 
Campbell Ritchie
Marshal
Posts: 63496
207
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:. . . Problem been unsolved for 2 hours and 1 minute, even though to fix it took only 1 minute. . . .

That is normal; fixing bugs is usually much easier than finding them.
 
D.J. Quavern
Ranch Hand
Posts: 81
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know how you guys do to implement egolessness! (now this discussion is outside the subject,but the issue is solved... But maybe I should open a new thread? It's actually super interesting and important).

People are very competitive at school, so even if you don't want to be stirred, you are. I have no qualms about discussing something I don't get in math, but in programming one feel judged very fast. And very self-conscious. And you can't really ask on stackoverflow where people will vote you down to the 7th level under ground .
I am very happy I found code ranch where your rules state just "be nice", and I think Junilu was very nice to me.

So any tips on relaxing the ego are welcome!
(shall I open a thread?)
So
 
Campbell Ritchie
Marshal
Posts: 63496
207
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Deja Quavern wrote:. . . So any tips on relaxing the ego are welcome!
(shall I open a thread?)
So

Sounds a good idea. Maybe (only maybe) our Soft Skills forum might be an appropriate home for it.
 
lowercase baba
Posts: 12727
51
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote: fixing bugs is usually much easier than finding them.



someone once told me there are two kinds of bugs:

1) Bugs that are hard to find, but easy to fix
2) bugs that are easy to find, but hard to fix.
 
Liutauras Vilda
Marshal
Posts: 6595
443
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

fred rosenberger wrote:someone once told me there are two kinds of bugs:

1) Bugs that are hard to find, but easy to fix
2) bugs that are easy to find, but hard to fix.


And probably those which haven't been discovered yet? But they should fall later on to those you specified.
 
Lasagna is spaghetti flvored cake. Just like this tiny ad:
Become a Java guru with IntelliJ IDEA
https://www.jetbrains.com/idea/
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!