Fun Coding Challenege

[wasab]

Hi, I got a fun coding challenge for those who like solving coding puzzle. This is actually from my today's homework assignment and solving it had been a blast. It was very rewarding. 

 

If anyone wants to try the challenge, here are the rules:

The problems themselves aren't very hard. However the tricky part is that sml is functional programming so no use of loop and mutable data state are allow. I don't believe anyone here will be interested in sml so feel free to use any language you want but it has to be functional programming so the challenge level is still there. This means all iterations can only be done with recursions, not loop and variables can not be assign a different value after being declared. Only pure functions are allowed and no use of third party libraries.

 

Have fun, whoever comes with a working solution will get a like from me . 

 

Edited April 26, 2018 by wasab
Edit out the irrelevent

[TLCH723]

"Under no circumstances are you allowed to copy code from the Internet to solve these problems"

[wasab]

Just now, TLCH723 said:

"Under no circumstances are you allowed to copy code from the Internet to solve these problems"

right. That is self obvious though. 

[Cruorzy]

4 hours ago, TLCH723 said:

"Under no circumstances are you allowed to copy code from the Internet to solve these problems"

He probably dind't read the post and just thought you wanted to people to make this for you.

[Dat Guy]

If anyone cares: Problems involving pairs and lists of numbers are easily solved with Lisp. I recommend that.

[wasab]

5 hours ago, Cruorzy said:

He probably dind't read the post and just thought you wanted to people to make this for you.

Well, I already solve and submitted the assignment and I am not asking anyone to code it in sml so no one will be helping me cheat. 

 

I just thought it is a fun little logic puzzle. 

 

[wasab]

I will upload my own solution in sml once the due date for the assignment is passed.

[Guest]

You guys could do a thread of problems and solving them like a little club. 
Similar to the under 100 line challenge. 
I was doing a programming log a while ago here doing problems: (Which Wasab already posted replies in haha. )

Spoiler

 

 

[wasab]

Okay, here are my solutions. It is not pretty but I am likely never going to write SML again in my entire life so who cares about learning to code pretty? 

(*--------------------------------helper functions -------------------------------------*)
(* Helper function rom the slide *)
fun length(L) =
if (L=nil) then 0
else 1+length(tl(L));

(* Helper function from the slide *)
fun reverse(nil) = 
nil | reverse(x::xs) = reverse(xs) @ [x];

(* Helper removing elements function *)
fun removing(list, numberOfElements) =
if numberOfElements = 0 then list
else removing(tl(list), numberOfElements - 1);

(* Helper get elements at index function *)
fun getElementAtIndex(list, index) =
if (index = 0) then hd(list)
else getElementAtIndex(tl(list), index - 1);

(* ----------------------------------------------Problem 1--------------------------------------------------- *)

(* Helper add fucntion for problem 1 *)
fun adding(initial, list, numberOfElements) =
if numberOfElements = 0 then initial
else adding(initial + hd(list), tl(list), numberOfElements - 1);

(* helper get result function for problem 1 *)
fun getResult(result, list, iterations) =
if iterations = 0 then result
else getResult(adding(0, list, 2)::result, removing(list, 2), iterations - 1);

(* Problem 1 *)
fun sumpairs(list) =
if length(list) mod 2 = 0
then reverse(getResult([],list, length(list) div 2))
else reverse(hd(removing(list, length(list)-1))::getResult([], list, length(list) div 2));

(* -----------------------------------------------Problem 2-------------------------------------------------- *)

(* Helper function for problem 2*)
fun lengthNotZero(list) = (length(list) > 0);

(* Helper function for problem 2*)
fun check(v1:int , v2:int) =
not (v1 = v2);

(* Helper function for problem 2*)
fun nextElementAdd(list) =
if length(list) > 1 then  
    if check(hd(list), hd(tl(list))) then false else true
else false;

(* Helper function for problem 2*)
fun getFirstDuplicates(result, list, add:bool) = 
if add then getFirstDuplicates(hd(list)::result, tl(list), nextElementAdd(tl(list)))
else if lengthNotZero(list) then hd(list)::result else result;

(* Helper function for problem 2*)
fun getResultFor2(result, elementsToRemove, list) = 
if length(list) = 0 then result
else getResultFor2(getFirstDuplicates([],list,nextElementAdd(list))::result, length(getFirstDuplicates([],list,nextElementAdd(list))), removing(list,length(getFirstDuplicates([],list,nextElementAdd(list)))));

(* Problem 2 *)
fun groupdupes(list) = reverse(getResultFor2([],0,list));

(* -----------------------------------------------Problem 3-------------------------------------------------- *)

(* Helper function for 3 *)
fun isPrime(i,x) =
if i = 1 then true
else if x mod i = 0 then false else isPrime(i-1,x)

(* Helper function for 3 *)
fun arePairsValid(x, y, z) = 
if x + y = z then true
else false;

(* Helper function for 3 *)
fun bruteForce(x, y, z) =
if x = z then ~1
else if arePairsValid(x,y,z) andalso isPrime(x-1,x) then x else bruteForce(x+1, y, z);

(* Helper function for 3 *)
fun getResultFor3(x,y,z) =
if(y > z) then []
else if bruteForce(x,y,z) > 0 andalso isPrime(y-1,y) then [bruteForce(x,y,z),y] else getResultFor3(x, y+1,z);

(* Problem 3 *)
fun goldbach(number) = getResultFor3(3,3,number);

(* -----------------------------------------------Problem 4-------------------------------------------------- *)

(* Helper function for 4 *)
fun converter(x) = 
if x <= 1 then [x] else converter (x div 2) @ [(x mod 2)];

(* Helper function for 4 *)
fun appendZeroes(list, count) =
if count = 0 then list else appendZeroes(0::list, count-1);

(* Helper function for 4 *)
fun getBitWise(result, greater, lesser, iteration) =
if iteration = 0 then result
else if getElementAtIndex(greater, iteration - 1) = 1 andalso getElementAtIndex(lesser, iteration - 1) = 1 
        then getBitWise(1::result,greater,lesser,iteration-1)  
            else  getBitWise(0::result,greater,lesser,iteration-1); 
            

(* Helper function for 4 *)          
fun Pre_bitwise(x,y) =
if length(converter(x)) > length(converter(y)) then getBitWise([],converter(x),appendZeroes(converter(y),length(converter(x))-length(converter(y))), length(converter(x)))
    else 
        if length(converter(y)) > length(converter(x)) then getBitWise([],converter(y),appendZeroes(converter(x),length(converter(y))-length(converter(x))), length(converter(y))) 
          else getBitWise([],converter(x),converter(y), length(converter(x)));
          
(* Problem 4 *)
fun bitwise_and(x,y) = 
if length(Pre_bitwise(x,y)) < 8 then appendZeroes(Pre_bitwise(x,y), 8 -length(Pre_bitwise(x,y))) else Pre_bitwise(x,y);



(*----------------------------------------------------------------------------test----------------------------------------------------------*)

(* 

***tests are for debuggging so commented out***

val t1 = sumpairs([8, 2, 3, 1, 5, 4])
val t2 = sumpairs([8, 2, 3, 1, 5, 4, 7])

val t3 = groupdupes([4,4,4,2,3,3,7,7,7,7,2,3,4,4,4])
val t4 = groupdupes([8,6,7,5]) 

val t5 = goldbach(4000)
val t6 = goldbach(3818)   

val t7 = bitwise_and(31, 12)
val t8 = bitwise_and(45, 172)
val t9 = bitwise_and(65, 255)        

*)  

 

[colonel_mortis]

My solutions to 1, 2 and 4 are

fun sumpairs (a::b::t) = (a+b) :: sumpairs(t)
  | sumpairs (l)       = l


fun group(a::b::t) =
    if a=b then let val (result, remainder) = group(b::t) in
        (a::result, remainder)
    end
    else ([a], b::t)
  | group(l) = (l, [])

fun groupdupes([]) = []
  | groupdupes(l) = let val (e, r) = group(l) in e::groupdupes(r) end


fun bitwise_and(0, 0) = []
  | bitwise_and(x, y) =
        bitwise_and(x div 2, y div 2) @ [if x mod 2 = 1 andalso y mod 2 = 1 then 1 else 0]

the bitwise_and function doesn't left pad it with 0s. I've made another (less elegant) version that does though

fun bitwise_and(x, y) = 
    let fun pad(l, 0) = l
          | pad(l, n) = pad(0::l, n-1)
        fun bwa_aux(0, 0, acc, depth) = pad(acc, 8-depth)
          | bwa_aux(x, y, acc, depth) =
                let val updated_acc = (if x mod 2 = 1 andalso y mod 2 = 1 then 1 else 0)::acc in
                    bwa_aux(x div 2, y div 2, updated_acc, depth + 1)
                end
    in bwa_aux(x, y, [], 0) end

 

[wasab]

9 hours ago, colonel_mortis said:

-snipe-

 

 

Your solution to the 4th problem failed one test. value for t7 should be [0,0,0,0,1,1,0,0] which is 8 bit. Otherwise, everything else works fine.

 

Edit: use the less elegant function for full mark  

 

Edited May 7, 2018 by wasab
See above