Target Sum Subarray

March 19, 2019

Given an array of non-negative integers, write a program that finds the contiguous portion of the array that sums to a given target, or report that there is no such subarray. For instance, in the array 1, 4, 20, 3, 10, 5, target 33 exists in the subarray 20, 3, 10, in the array 1, 4, 0, 0, 3, 10, 5, target 7 exists in the subarray 4, 0, 0, 3, and in the array 1, 4, target 3 does not exist in any subarray.

Your task is to write a program that finds a target sum in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

Today’s exercise is simple, but leads me to ask a question. Here is the exercise, taken directly from /r/learnprogramming:

Draw the hierarchy chart and then plan the logic for a program needed by the sales manager of The Henry Used Car Dealership.

  1. The program will determine the profit on any car sold. Input includes the sale price and actual purchase price for a car.
  2. The output is the profit, which is the sale price minus the purchase price.
  3. Use three modules. The main program declares global variables and calls housekeeping, detail, and end-of-job modules.
  4. The housekeeping module prompts for and accepts a sale price. The detail module prompts for and accepts the purchase price, computes the profit, and displays the result. The end-of-job module displays the message Thanks for using this program.

I have written the actual program, but I am struggling with the hierarchy chart. Can someone give me any guidance on this one?

Is this for real? Separate modules for each statement? Why does the detail module get input, compute profit and display the result? If you have to have separate modules to ask for the purchase price and say thank you, why not split getting the sale price, computing the profit, and printing the result into separate modules? Is this how programming students are taught these days? To take a fundamentally simple program and make it ridiculously complex by splitting it into modules? What would David Parnas say about this modularization?

Your task is to write a program to compute profit for The Henry Used Car Dealership; you might also help me understand the way this program is intended to be modularized. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Recursion

March 12, 2019

Although we sometimes discuss rather more advanced topics, one focus of this blog will always be on student programmers, so I monitor several internet sites that cater to questions from learners. I have seen several posts in the last week or so about recursion, so I assume that we have reached the point in the semester where programming students are learning about recursion. Most programming professors seem to think that the factorial function (what is the value of n factorial) and the fibonacci function (what is the nth fibonacci number) are good demonstrations of recursion; personnally, I think it is better to discuss recursion in terms of binary trees.

Your task is to write versions of the factorial and fibonacci functions that use recursion to calculate their result. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Frequency Counts

March 8, 2019

Today we have a tricky exercise from Geeks For Geeks:

Given an unsorted array of n integers from 1 to n, possibly with some items appearing multiple times and others missing from the array, count the frequency of all items that are present. Your solution must run in O(n) time and take O(1) extra space.

Your task is to write a program to count frequencies as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have something unusual today: a turing machine built from a business card that I learned about on Reddit. I immediately stopped and built my own, and had a lot of fun, and I suspect many of my readers will feel the same way.

Your task is to build your own turing machine. No coding, just playing. Feel free to discuss the exercise in the comments below.

Jumble

March 1, 2019

Last week I gave a rather silly solution to the Scrabble problem. Today’s exercise is my penance for that silliness.

As I’ve mentioned previously, my day job is on a team of programmers that supports our enterprise-wide computer system. I sit in a cube farm, where there is neither audible nor visual privacy. We recently hired a new programmer to replace a retiring team member, and he has a daily calendar on his desk that provides a jumbled series of letters that you have to rearrange to form a word. Yesterday’s puzzle was L T E A D E; most of the puzzles I solve in a few seconds, but that one took several minutes. The calendar appears to have a flaw: the solutions, one day after the next, are in alphabetical order, so I know before I start that the first letter will be E.

Your task is to write a program that solves jumbles. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

ATM Machine

February 26, 2019

Today’s exercise asks you to simulate an ATM machine:

  1. Prompt for userid and password. If userid and password are not in the database, reprompt.
  2. Display balance.
  3. Present a menu asking to deposit, withdraw or exit. If user selects withdraw or deposit, perform the indicated transaction and goto Step 2. Deny withdrawals that would overdraw the account.
  4. Exit the program.

Your task is to write a program to simulate an ATM machine. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Scrabble

February 22, 2019

Today’s task is based on the game of Scrabble.

Your task is to write a program to find the dictionary words of length 2 to 7 that can be formed from the letters Q O F T H E A. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

The Trapped Knight

February 19, 2019

Over at Numberphile, Neil Sloane discusses a knight moving on an infinite chessboard with squares numbered in a square spiral (note that, starting from 1, the squares on the southeast diagonal are successive squares of odd numbers 1² = 1, 3² = 9, 5² = 25, 7² = 49, and so on):

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28 .
41 20  7   8 9 10 27 .
42 21 22 23 24 25 26 .
43 44 45 46 47 48 49 50

The knight starts from square 1 and always moves to the smallest-numbered square not previously visited. Thus, from 1, the knight can move to squares 10, 12, 14, 16, 18, 20, 22 or 24, of which the smallest unvisited square is 10. From 10, the knight can then move to squares 1, 3, 23, 29, 47, 49, 51 or 53; the smallest of those, 1, has already been visited, so the knight moves to square 3. And so on. The beginning of the knight’s tour visits squares 1, 10, 3, 6, 9, 4 and so on (A316667).

Your task is to write a program to determine if the knight’s tour is infinite or if the knight becomes trapped with no remaining unvisited squares; if the knight becomes trapped, determine the length of his tour and the square on which he remains. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Peaks

February 15, 2019

Given an array of integers, a peak is a subarray of minimal length in which the integer values increase and then decrease. For instance, in the array [5,5,4,5,4] there is a peak [4,5,4] and in the array [6,5,4,4,4,4,4,5,6,7,7,7,7,7,6] there is a peak [6,7,7,7,7,7,6]. Note that [4,5,6,7,7,7,7,7,6] shows a pattern of increasing and decreasing values, but it is not minimal because the first two items can be removed and the remaining subarray remains a peak. The array [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8] has two peaks, [4,5,4] and [8,9,9,8].

Your task is to write a program that finds all of the peaks in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2