Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Can you please help fix the functions last_card in both code files and only leftover_count in hw.ml code to match the task out put in

Can you please help fix the functions last_card in both code files and only leftover_count in hw.ml code to match the task out put in OCaml program, please don't use AI to fix the code, it does not give correct output:

hw3_rec.ml: Should contain solutions to P1, P2, and P3. Use of recursion is optional (i.e. use of rec in function declarations).

hw3.ml: Should contain solutions to P1, P2, and P3 without the use of recursion by using calls to List.fold_left. For this file, no points will be awarded if rec is detected. Hint: it may help to write a helper accumulator function to use as an input to the List.fold_left call.

P1) leftover_count : int list -> int -> int =

Suppose we have a shuffled deck of numbered cards. Consider a card game where you select an initial number, and discard a batch of that size (or fewer, if not enough cards remain) from the top of the deck. The top card becomes the new number, and the process repeats. For example, if the top card is two, that card and the next card are discarded and the next card flipped over. The problem is to find the number of cards that still need to be discarded once the bottom of the deck is reached and there are no more cards to discard.

Function leftover_count takes in an integer list lst and an integer x, and outputs an integer. Input lst acts as the deck of cards, and x is the initial number, which can be thought of as the counter. A sketch of a possible implementation: each time the counter decrements, discard the first element in the list, so long as the list is non-empty. If the counter hits 0 and the list is non-empty, reset the counter with the value of the current element. If the list is empty, return the current value of the counter.

Assume the list contains only positive integers.

To illustrate, suppose lst = [1;4;2;10;1;4;2;10] and x = 2. At each step, decrement the counter and discard the head element in the list.

Counter = 2, lst = [1;4;2;10;1;4;2;10]

Counter = 1, lst = [4;2;10;1;4;2;10]

Counter = 0, lst = [2;10;1;4;2;10]; reset, Counter = value of current element = 2

Counter = 1, lst = [10;1;4;2;10]

Counter = 0, lst = [1;4;2;10]; reset, Counter = value of current element = 1

Counter = 0, lst = [4;2;10]; reset, Counter = value of current element = 4

Counter = 3, lst = [2;10]

Counter = 2, lst = [10]

Counter = 1, lst = []; empty list, return Counter.


Expected Output:

So in this example, leftover_count [1;4;2;10;1;4;2;10] 2 = 1

Similarly,

leftover_count [1;4] 5 = 3

leftover_count [1;4] 2 = 0

leftover_count [1;4;2;10;3;5;7;11] 3 = 5

leftover_count [1;4;2;10;3;5;7;11] 5 = 2

leftover_count [1;4;2;10;3;5;7;11] 7 = 10



P2) last_card : int list -> int -> int =

Similar to P1, except the function should return the value of the last position (last selected card) where the counter reset. If the initial counter value does not point to a valid position in the list (i.e. initial value larger than the size of the list), return -1.

Expected Output:

last_card [1;4] 5 = -1

last_card [1;4] 1 = 4

last_card [1;4;2;10;3;5;7;11] 1 = 5

last_card [1;4;2;10;3;5;7;11] 3 = 10
last_card [1;4;2;10;3;5;7;11] 7 = 11

hw3_rec.ml code:

(* P1 *)

let leftover_count lst x =

let rec count_discarded counter deck =

match (counter, deck) with

| (0, hd :: tl) -> count_discarded (hd -1) tl

| (_, hd :: tl) -> count_discarded (counter - 1) tl

| (_, []) -> counter

in

count_discarded x lst


(* P2 FIX ME*)

let last_card lst x =

let rec find_last_position counter last_pos deck =

match (counter, deck) with

| (_, []) -> if counter = 0 then last_pos else -1

| (0, _ :: tl) -> find_last_position (x - 1) (List.length lst - x) tl

| (_, hd :: tl) -> find_last_position (counter - 1) (last_pos + 1) tl

in

if x > List.length lst then -1 else find_last_position x (-1) lst


(* P3 *)

let num_greater_than_sum lst =

let rec count_greater_than_sum count sum = function

| [] -> count

| hd :: tl ->

if hd > sum then

count_greater_than_sum (count + 1) (sum + hd) tl

else

count_greater_than_sum count (sum + hd) tl

in

count_greater_than_sum 0 0 lst


hw3.ml Code:

(* P1 FIX ME*)

let leftover_count lst x =

let folder (counter, remaining_cards) _ =

if counter >= List.length remaining_cards then (0, [])

else if counter = 0 then (List.hd remaining_cards, List.tl remaining_cards)

else (counter - 1, List.tl remaining_cards)

in

let _, remaining_cards = List.fold_left folder (x, lst) lst in

List.length remaining_cards


(* P2 FIX ME*)

let last_card lst x =

let folder (counter, last_pos, _) el =

if counter = 0 then (el - 1, last_pos, el)

else (counter - 1, last_pos + 1, el)

in

let final_counter, _, last_card = List.fold_left folder (x, -1, -1) lst in

if final_counter = 0 then last_card

else -1


(* P3 *)

let num_greater_than_sum lst =

let folder (sum, count) el =

if el > sum then

(sum + el, count + 1)

else

(sum + el, count)

in

let (_, result_count) = List.fold_left folder (0, 0) lst in

result_count

Please don't use AI and explain what changes were made.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Business Communication Essentials a skill based approach

Authors: Courtland L. Bovee, John V. Thill

6th edition

978-0132971324

More Books

Students also viewed these Programming questions