Can this snippet be written without an Exit For?

[mathwizard44]

The aim of this snippet is to have the user type 4 integers from 1 to 100 into an array called nums(), so that all the numbers are different from each other. It took me perhaps 2 hours of thought and trial and error to come up with this snippet.

Code: Select all

    nums(1) = GetInt(1, 100)
    For i = 2 To 4
        Do
            accept = 0
            n = GetInt(1, 100)
            For j = 1 To i - 1
                If n = nums(j) Then
                    accept = 0
                    Exit For
                Else
                    accept = 1
                End If
            Next j 
            If accept = 0 Then Print "You already picked that! Try again."
        Loop While accept = 0
        nums(i) = n
    Next i

This snippet runs correctly without incident. So I guess my question is more of a general algorithm question: is there a way to write this snippet without using "Exit For" and the variable "accept"? I have no quarrel with those things (and hey, it works!), but from what I remember from programming class, any looping procedure could be written without "Exit For" (which would be "break" in C from what I remember).

I guess it's just driving me crazy that I couldn't transform this code when my training says that it could be transformed. Any insight will be much appreciated.

Romel

P.S. Yes, this is kind of like a homework assignment thing, but the issue I am asking about is not relevant to the homework. It's a small part of a project in Probability that I'm completing.

P.P.S. GetInt() is a function that accepts an integer from the user but checks whether the number is between the bounds specified in the arguments. So GetInt(1, 100) will say "Try again" if you entered 129 or 0.

[HD_]

Something like this could work (untested):

Code: Select all

    nums(1) = GetInt(1, 100)
    i=1
    while (i<=4)
        n=GetInt(1,100)
        j=1
        while (j<i-1)
            if (n=nums(i)) then
                print "You already picked that! Try again."
                n=GetInt(1,100)
                j=1
            endif
            j+=1
        wend
        nums(i)=n
        i+=1
    wend

Could be cleaner with for loops, but I wasn't sure if people dislike seeing for loops abused like that.

[j_milton]

Code: Select all

dim as integer count, valid_count, n, nums(1 to 4)

nums(1) = getint(1,100)
valid_count = 1
do
  n = getint(1,100)
  for count = 1 to valid_count
    if nums(count) = n then
      print"sorry, that number has been picked, try again"
      n = 0
    endif
  next
  if n <> 0 then
    valid_count += 1
    nums(valid_count) = n
  endif
loop until valid_count = 4

[mathwizard44]

Come to think of it, my snippet seems like an abuse of the For loop. ^_^ Thanks for the suggestion, guys. I will test both these out.

[KristopherWindsor]

You don't need all that code. :)

Code: Select all

function getint(l as integer, u as integer) as integer
  dim as integer x
  input "number please", x
  if x < l then x = l
  if x > u then x = u
  return x
end function





dim as integer nums(1 To 4), used(1 to 100)

for i as integer = 1 to 4
  nums(i) = getint(1, 100)
  if used(nums(i)) then
    i -= 1
    Print "sorry, that number has been picked, try again"
  else
    used(nums(i)) = -1
  end if
next i

[agamemnus]

Here's what you should do. This is similar to the above code but doesn't use a function.

The number is in a range 1-100: "dim picked(1 to 100) as uinteger"

Full code: (untested)

Code: Select all

dim as integer minvalue = 1, maxvalue = 100
dim picked(minvalue to maxvalue) as uinteger
dim i as integer
dim curPicked as uinteger
for i = 1 to 10
 curPicked = getInt(minvalue, maxvalue)
 if picked(curPicked) then
  print "You already picked that!": i-=1
 else
  picked(curPicked) += 1
 end if
next i

[j_milton]

You don't need all that code. :)

function getint(l as integer, u as integer) as integer
dim as integer x
input "number please", x
if x < l then x = l
if x > u then x = u
return x
end function

This function will accept a value that is out of legal range as defined in the problem (bug) and force it into range (bug) without advising the user that it has done so (very bad style)

[KristopherWindsor]

This function will accept a value that is out of legal range as defined in the problem (bug) and force it into range (bug) without advising the user that it has done so (very bad style)

Hm? I was assuming getint() was already written, but I needed a substitute to test the program.
The actual getint() should work like this:

Code: Select all

function getint(l as integer, u as integer) as integer
  dim as integer x
  input "number please", x
  if x < l or x > u then
    print "that number is out of range"
    return getint(l, u)
  end if
  return x
end function

The return value for getint() was not specified for when the user enters a number out of range, so this function is valid.

[j_milton]

Here's what you should do. This is similar to the above code but doesn't use a function.

The number is in a range 1-100: "dim picked(1 to 100) as uinteger"

Full code: (untested)

Code: Select all

dim as integer minvalue = 1, maxvalue = 100
dim picked(minvalue to maxvalue) as uinteger
dim i as integer
dim curPicked as uinteger
for i = 1 to 10
 curPicked = getInt(minvalue, maxvalue)
 if picked(curPicked) then
  print "You already picked that!": i-=1
 else
  picked(curPicked) += 1
 end if
next i

This code prompts the user to input 10 numbers, not 4 as defined in the problem (bug) and does not store the valid picks in an array called "nums" as specified in the problem (bug)

[HD_]

Nice, I like the other suggestions too ;)

[adhay]

Here ya go.

Code: Select all

dim flag(100)
n=getint (1, 100)
flag(n)=1
num(1)=n
i=2

while i<5
    n=getint(1, 100)
    if flag(n)=1 then
        Print "You already picked that! Try again."
    else
        flag(n)=1
        num(i)=n
        i+=1
    endif
wend
    

[mathwizard44]

Well, this has been quite an exercise, and for me as well. After looking at your snippets and some thought (some of which I did while I was trying to answer my Analysis test!) I came up with my own fixed snippet. It doesn't do away with the "accept" variable but it refrains from calling "Exit For" or "Exit" anything, for that matter:

Code: Select all

Declare Function GetInt(ByVal l As Integer, ByVal h As Integer) As Integer

Dim As Integer i, j, accept
Dim As Integer nums(1 To 8)

nums(1) = GetInt(1, 100)
For i = 2 To 4
    Do
        nums(i) = GetInt(1, 100)
        j = i - 1
        accept = 1
        Do
            If nums(i) = nums(j) Then accept = 0
            j -= 1
        Loop Until j = 0
        If accept = 0 Then Print "You already picked that! Try again."
    Loop While accept = 0     
Next i

Print nums(1), nums(2), nums(3), nums(4)

End

Function GetInt(ByVal l As Integer, ByVal h As Integer) As Integer

Dim As Integer i, bounded

bounded = 0

Do
    Input i
    If (i < l) Or (i > h) Then
        Print "Out of bounds; ";
        Print "type a number between"; l; " and"; h; "."
    Else
        bounded = 1
    End If
Loop While bounded = 0

GetInt = i

End Function

You can also see the GetInt function I wrote (whose absence in my original post caused a small controversy ^_^), which involves another flag "bounded". My code is full of flags like this; you use what you see, I guess, and I saw lots of flag variables.

Anyway, I now have a greater appreciation of the tradeoffs involved in writing code. The snippets so far seem to fall into two categories:

• using a flag variable (such as j_milton's "valid_count" and my "accept")
• using a flag array (such as adhay's "flag()", agamemnus' "picked()", and KristopherWindsor's "used()")

There are the mavericks, of course: KristopherWindsor's snippet manipulates the value of the counter variable (i) within the For loop, and HD_'s example does without For loops and uses only 2 variables (against my 3).

When I compare my "before" and "after" snippets, I realize that I got loop "closedness" while sacrificing time. In my new code, after the user enters the 4th number, the innermost Do loop will run 3 times, whereas if I had just done "Exit Do" as soon as I got a match, I would have saved a few instruction cycles. Granted, it is microscopic savings in terms of today's processors, but still a savings. (Apologies are in order as I am a mathematician by training, so a small number is still a number. ^_^)

Also, after looking at the examples, while having a flag array would become more economical if more numbers need to be entered, I decided that the flag variable is the way to go. The savings in this case are considerable: Why set aside space for 100 integers when you can enforce uniqueness on the inputs by using one integer? Again, I realize that it depends on the situation. With a flag array, the uniqueness check only runs once no matter how many numbers are needed. Under the flag variable situation, if I instead asked for 50 numbers, when the user enters the 50th number, the program will have to check the nums array 49 times!

Thanks again for all the inputs. I feel I've learned a great deal in this thread.

P.S. Not the least of which is the interesting idea from KristopherWindsor's snippet for GetInt. ^_^ I never would have thought of using recursion in this manner, yet it is intriguing! My only worry would be running out of stack space if the user couldn't get his or her act together and come up with a bounded integer after umpteen tries. ^_^ There needs to be another use for this; I will keep this in mind for later.

[KristopherWindsor]

You're a mathematician, but I'm a Computer Scientist. ;)

It might seem careless that I didn't fully optimize everything, but I knew that the program would still be efficient enough:

• The 100-element array takes less than 1K of memory. If it took more than 100K, I would have used "Dim Shared" to get it off the stack, and if it took more than 10M, I would have considered a more memory-efficient solution. A more efficient solution would be an actual hashset, but FB doesn't have those built-in. I based my idea on the use of hashsets, which are frequently used for algorithm-type coding.
• The recursive trick in GetInt() comes from some Scheme work I did last semester. Scheme is an interpreted language where performance doesn't matter much. But based on the amount of memory put on the stack for each function call, and the 1MB stack size, it is OK if the recursion goes more than 10,000 levels deep. This limit will probably never be reached.

Also it may seem like a trick to decrement a variable used by a for loop, but you really should know how the loops work. It's not really a trick, particularly since for loops in other languages look like "for (...;...; i++)" where the increment is explicitly given.
In C you could write it as:

Code: Select all

int i;
for(i = 0; i < 4; )
  if (used[nums[i] = getint(1, 100)])
    printf("sorry, that number has been picked, try again\n");
  else
    used[nums[i++]] = 1; // mark as used, then increment i

[j_milton]

Mathwizard:

You thinking in your last post is good. A few more things to consider...

Obviously this is a program with small numbers of inputs, and a small range of valid inputs, so either of the approaches is "fine", but there is lots of evil done in the name of supposed "efficiency" which this example suggests if we were to scale it up to larger values.

For example, while it is true that approaches like KristopherWindsor's do not require you write code to check each prior pick like mine does the computer does have to initialize each of those 1000 array cells to zero when the program runs. If the range of valid inputs was 1..1000000 then it would have to initialize a million locations to zero and so on. Point being when considering code "efficiency" remember the code that is implied by things like dimensioning an array.

There are lots of things that can be written which will compile, and which will run "bug free" i.e. behave in the way the programmer intended. That does not mean that as a matter of course one should use all of them :-) Manipulating the counter variable in a for..next loop in the middle of the loop somewhere is, in my opinion, one of those things, its "bad style". Try to get into the habit of writing code as if someone else might be expected to be able to work with it in the future
just by looking at the code itself.

Some axioms on "efficiency" from the book: "Elements of Programming Style" which may serve you well:

- Make it right before you make it faster.
- Make it fail-safe before you make it faster.
- Don't sacrifice clarity for small gains in "efficiency"
- Let your compiler do the simple optimizations.
- Keep it simple to make it faster.
- Don't diddle code to make it faster, find a better algorithm.
- Instrument your programs. Measure before making efficiency changes.

[mathwizard44]

KristopherWindsor:

Very nice. It never did occur to me that the increment was explicit in the for-loop in C. And yes, I did not doubt that this snippet exercise was small enough such that we did not have to worry too much (at all, even!) about having to run a loop 49 times or keeping 100 integers in an array. I guess the hypersensitivity to inefficiency was inculcated in me by my computer science professors (I had 2 or three) and the thick books I read. ^_^ No doubt I should have calculated the overhead imposed by the different strategies--if I had, it would have occurred to me that the tradeoffs are infinitesimal, especially on today's hardware. At any rate, just as in every other time I post a question here, I come out with armloads more full of tricks and insights than I ever expect, and I grow richer for it.

Oh, and my experience in Scheme is limited to my seeing it sometimes when writing functions for Lilypond, the music-typesetting program.

j_milton:

When you mentioned that someone might be looking at the code later, trying to figure out how it worked, I realized that it was that thought that sent me here to pose this question in the first place. The original snippet was the first time I ever had to use a break out of a loop, and perhaps for that reason I thought it looked weird. ^_^

But now, comparing the two, I much rather prefer having the "Exit For", as that is what a human would do. As they sometimes say about lost objects, "You find it at the last place you look." When you find it, you should stop looking.

I'm glad I'm finally having these conversations with other people who program in FreeBASIC. I'm beginning to see what my professor said about how writing just one program can teach you more than reading the whole syntax reference. And, somewhat ironically, this thread ended up convincing me of the wisdom of breaking out of loops. ^_^ (Though I am keeping my "after" snippet for my program.)

Thanks again, everyone.