• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
  • entry
    1
  • comments
    0
  • views
    2236

Inserting a letter recursively

Sign in to follow this  
Followers 0
Alpha_ProgDes

1004 views

NOTE: This is not complete. Touch ups, corrections, and changes will be made. This may be an article in the first future. But this is more of me working through the logic of a problem I was working on earlier last week and this week. And I'm sharing.



(ins-one w (list e a r));(w e a r);(e w a r);(e a w r);(e a r w)
must be in this order

function needed to make [rest of lists]

what we know:
letter to insert, (we'll call ins-ltr)
the original list (list e a r), (we'll call inserting-list)
therefore there will be (first inserting-list) (rest inserting-list)


what is the base case? (ins-one "w" empty)
we know that the function returns a list of lists
so it would return (list (list "w"))

so now we know this:(define (ins-one ins-ltr inserting-list) (cond [(empty? inserting-list) (list (list ins-ltr))] [else ... ins-ltr ... inserting-list ... (cons ins-ltr inserting-list) ; example (cons "w" (list "e" "a" "r")) ... (first inserting-list) ... (rest inserting-list)]))
since we are solving this recursively we know that [ins-one] has to be applied to the rest of [inserting-list](define (ins-one ins-ltr inserting-list) (cond [(empty? inserting-list) (list (list ins-ltr))] [else ... ins-ltr ... inserting-list ... (cons ins-ltr inserting-list) ; example (cons "w" (list "e" "a" "r")) ... (first inserting-list) ... (ins-one ins-ltr (rest inserting-list))]))
we also know that there is an auxilary function that creates [rest of lists], (we'll call it f1, for now)

so this first iteration would look like(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "e" "a" "r")) (list (list "w"))] [else ... "w" ... (list "e" "a" "r") ... (cons "w" (list "e" "a" "r") ... (first (list "e" "a" "r")) ; (first (list "e" "a" "r")) = "e" ... (ins-one "w" (rest (list "e" "a" "r")))])) ; (rest (list "e" "a" "r")) = (list "a" "r")
the next-2 iteration of this function will work on (list a r)
so (ins-one ins-ltr (list a r)) will create(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "a" "r")) (list (list "w"))] [else ... "w" ... (list "a" "r") ... (cons "w" (list "a" "r") ... (first (list "a" "r")) ... (ins-one "w" (rest (list "a" "r")))]))
the next-3 iteration would be(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... "w" ... (list "r") ... (cons "w" (list "r") ... (first (list "r")) ... (ins-one "w" (rest (list "r")))]))
the last iteration would be(define (ins-one ins-ltr inserting-list) (cond [(empty? empty) (list (list "w"))] [else ... "w" ... (empty ... (cons "w" empty) ... (first empty); you can't (first empty) ... (ins-one "w" (rest empty))])) ; you can't (rest empty)
Because the last iteration returns (list (list "w")), so iteration next-3 now looks like(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... "w" ... (list "r") ... (cons "w" (list "r") ... (first (list "r")) ... (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))
We know based on earlier analysis of the data that [f1] will create [rest of lists]. We also know
that the first list of (ins-one "w" (list "e" "a" "r")) is (list "w" "e" "a" "r").

Therefore the general shape is: (cons (list "w" "e" "a" "r") [rest of lists])
or
(cons (list "w" "e" "a" "r") [f1])

Now that last iteration has returned the inserted letter as a new list of lists (list (list "w")),
we now can begin to construct [rest of lists].

In the template, I have all the values and calls that could be used. So let's see if we can remove whatever we don't need.
We are going to keep (cons ins-ltr inserting-list) and (ins-one ins-ltr (rest inserting-list)), for the reasons already mentioned.
[ins-ltr] is being used in the two functions that we are keeping and seems to have no use outside of that. So we'll remove it.
Also, [inserting-list] is also being used in the two functions and also seems to have no use outside of that. So we'll remove that as well.

So now our template with the next-3 iteration data looks like:(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... (cons "w" (list "r") ... (first (list "r")) ... (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))
To construct [rest of lists] (first (list "r")) and (list (list "w")) will have to be used somehow. [f1] will use both of these values.
Since (first (list "r")) comes out to be "r", we can say that the first argument will be a letter. And (list (list "w")) will be a list of lists.
So the second argument will be a list of lists. So now our template for this auxilary function will look like:(define (f1 a-letter list-of-lists) (cond [(empty? list-of-lists) ...] [else ... a-letter ... list-of-lists ... (first list-of-lists) ... (rest list-of-lists)]))
And the template for [ins-one] now looks like this:(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... (cons "w" (list "r") (f1 (first (list "r")) (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))
Using next-3 iteration, let's look at the values we have so far:

a-letter -> "r"
list-of-lists -> (list (list "w"))
(first list-of-lists) -> (list "w")
(rest list-of-lists) -> empty

Let's look at the data:

(w e a r)
(e w a r)
(e a w r)
(e a r w)

We know that the first iteration of [ins-one] will give the first list and [rest of lists].
The second iteration of [ins-one] will give the second list and [rest of lists].
The third iteration of [ins-one] will give the third list and [rest of lists].
The fourth iteration of [ins-one] will give the fourth list.

[rest of lists] gives us partial lists which are passed to the previous recursive call to make those lists more complete.

The fourth iteration gives (list (list "w")). The third iteration gives the third list (cons "w" (list "r"))
and the [rest of lists] (f1 "r" (list (list "w"))). As we can see, the third iteration gives us a partial list of the third list.
As well as having [f1] work on "r" and partial list of lists (list (list "w")) of the fourth list.

[f1] produces a list of lists which is more complete as the previous recursive calls execute. We know that the partial list of the fourth list
must produce (list "r" "w"). A straightforward way to handle that is (cons "r" (list "w")) or (cons a-letter (first list-of-lists)). And since
this is a list-of-lists and [f1] must work on list-of-lists recursively.

So now our [f1] template looks like the following:(define (f1 a-letter list-of-lists) (cond [(empty? list-of-lists) ...] [else (cons a-letter (first list-of-lists)) ... list-of-lists (f1 a-letter (rest list-of-lists))]))
Now we know that [f1] should return a list of lists. Also based on the fourth list, this list of lists should be (list (list "r" "w")).
So that means when (f1 "r" empty) is called it should return empty. Now we know what the base case is. And with that we know we can remove
the standalone list-of-lists. And lastly we know what the structure of [f1] will be.(define (f1 a-letter list-of-lists) (cond [(empty? list-of-lists) empty] [else (cons (cons a-letter (first list-of-lists)) (f1 a-letter (rest list-of-lists)))]))
What we said earlier is that the first list is the first list of a list of lists. To make that happen, we have to combine the two.
So now the template with the next-3 iteration data is the following:(define (ins-one "w" (list "r")) (cond [(empty? (list "r")) (list (list "w"))] [else (cons (cons "w" (list "r")) (f1 (first (list "r")) (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))
The actual code for [ins-one] is:(define (ins-one ins-ltr inserting-list) (cond [(empty? empty) (list (list ins-ltr))] [else (cons (cons ins-ltr inserting-list) (f1 (first inserting-list) (ins-one ins-ltr (rest inserting-list))))]))

2
Sign in to follow this  
Followers 0


0 Comments


There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now