Answers to deleted StackOverflow Questions

How to sum up the digits of number in Racket?

“Design a Racket function named sumDigit that takes a number and sum the digit/s of given number. sumDigit: number → number”

So this is the question. I can’t think a way of doing this at the moment. I know its easy tho. Can you help me about this? Thanks :)

Answer:

Modulo gets the last digit, and division by 10 and floor gets all but the last digit:

(define (sum-digits n)
  (if (= n 0)
      0
      (+ (modulo n 10) (sum-digits (floor (/ n 10))))))

How to prove theorem plus_n_n_injective in Logical Foundations (Tactics Chapter)?

Theorem plus_n_n_injective : forall n m,
     n + n = m + m ->
     n = m.

Answer:

Solution removed on the request of Arthur Azevedo De Amorim.

How do I sort a list of coordinates (x,y) using their sums

How do I sort a list of coordinates (x,y) using their sums in Dr. Racket/Scheme

(sort-points (list (list 2 1) (list 0 0)
(list 0 3) (list -2 4))
=> (list (list 0 0) (list -2 4) (list 0 3) (list 2 1))

Comment:

(define (my-sort alon)
  (cond [(empty? alon) empty] [ else (insert (first alon) (my-sort (rest alon)))]))

(define (insert n alon)
  (cond [(empty? alon) (cons n empty)]
        [ else (cond [(<= n (first alon)) (cons n alon)]
                     [ else (cons (first alon) (insert n (rest alon)))])])) 

Answer:

You can just pass along a comparator into sort which tells it how to sort the elements in the list.

#lang racket

(sort (list (list 2 1) (list 0 0) (list 0 3) (list -2 4))
      (λ (x y) ; less-than?
        (<= (+ (first x) (second x))
            (+ (first y) (second y)))))
; => '((0 0) (-2 4) (0 3) (2 1))

Edit 1: Without lambda:


(define (my-sort l)
  (define (cmp x y)
    (<= (+ (first x) (second x))
        (+ (first y) (second y))))
  (sort l cmp))

(my-sort (list (list 2 1) (list 0 0) (list 0 3) (list -2 4)))
; => '((0 0) (-2 4) (0 3) (2 1))

Edit 2: By modifying the code you provided (in the comment):

#lang racket

(define (my-sort alon)
  (cond [(empty? alon) empty]
        [else (insert (first alon) (my-sort (rest alon)))]))

(define (insert n alon)
  (cond [(empty? alon) (cons n empty)]
        [else (cond
                ; note: changed <= to cmp 
                [(cmp n (first alon)) (cons n alon)]
                [else (cons (first alon) (insert n (rest alon)))])]))

(define (cmp x y)
  (< (+ (first x) (second x))
     (+ (first y) (second y))))


(my-sort (list (list 2 1) (list 0 0) (list 0 3) (list -2 4)))
; => '((0 0) (-2 4) (0 3) (2 1))

Creating all possible trees

Before I describe the function I want to write, I will provide some data definitions.

;; An Op (Operator) is an (anyof '+ '- '* '/).

;; A BET (Binary Expression Tree) is either a:
;; * Nat
;; * (list Op BET BET)

So I want to implement the function make-all-bets, which consumes a list of permutations of a list of numbers and a list of $n$-tuples of operators and produces a list of all possible BET’s using the provided permutations and $n$-tuples, considering all possible tree structures.

Note: the function requires that the length of each list in the first list the function consumes is 1 greater than the length of each list in the second list the function consumes. The contract below should make things easier to understand.

;; (make-all-bets nln nlp) produces a list of all possible BET's
;;   using nln nlp.
;; make-all-bets: (listof (listof Num)) (listof (listof Op)) -> (listof BET)
;; requires: (length nln) - (length nlp) = 1

Also, the following check-expects give an idea of what the function should produce:

(check-expect
 (make-all-bets
  '((8 6 4 2))
  '((/ + -)))
 '((/ 8 (+ 6 (- 4 2)))
   (/ 8 (+ (- 6 4) 2))
   (/ (+ 8 6) (- 4 2))
   (/ (+ 8 (- 6 4)) 2)
   (/ (+ (- 8 6) 4) 2)))
(check-expect
 (make-all-bets
  '((8 6 2))
  '((/ +)))
 '((/ 8 (+ 6 2))
   (/ (+ 8 6) 2)))

A hint I was given was that I need to consider all the ways to partition $n–1$ nodes b/w the left and right subtrees of a node and then, through recursion, build the left and right subtrees. For a given n, there are $C_n$ possible trees, where $C_n$ is the $n$th Catalan number, calculated by $\prod_{k=2}^n \dfrac{n+k}{n}$. Also, nested calls to map are apparently helpful. It also might be helpful to take two intermediate steps:

  1. Implement a function (make-left-right-pairs node-cnt) that produces a list of number-pairs indicating the size of the left and right subtrees for a given overall-node-count on a tree. For instance, the following check-expects should be satisfied
(check-expect (make-left-right-pairs 3) '((2 0) (1 1) (0 2)))
(check-expect (make-left-right-pairs 4) '((4 0) (3 1) (2 2) (1 3) (0 4)))
  1. Implement (make-tree-structure node-cnt) which produces a list of trees w/o putting in the values for internal nodes (operators) and leaves (numbers). Each node value represents the number of nodes. For instance, consider the following check-expect:
(check-expect (make-tree-structure 3)
              '((3 empty (2 empty (1 empty empty)))
                (3 empty (2 (1 empty empty) empty))
                (3 (1 empty empty) (1 empty empty))
                (3 (2 empty (1 empty empty)) empty)
                (3 (2 (1 empty empty) empty) empty)))

So I can implement the two helper functions, but I don’t know how to combine the helper functions to create the function (make-all-bets nln nlp). I can see how the function’s output resembles the output of (make-tree-structure), but I don’t know how to implement that into code. Any help would be appreciated (no code for the helper functions is necessary since I already know how to implement them).

Answer:

Looks like once you get the result of your second helper — make-tree-structure — you can simply map all the nodes to operators and the leaves to numbers within each tree in the list.

#lang htdp/isl+

(require 2htdp/abstraction)

(define tree-structure
  '((3 empty (2 empty (1 empty empty)))
    (3 empty (2 (1 empty empty) empty))
    (3 (1 empty empty) (1 empty empty))
    (3 (2 empty (1 empty empty)) empty)
    (3 (2 (1 empty empty) empty) empty)))

(check-expect (map-all-trees tree-structure '(/ + -) '(8 6 4 2))
              '((/ 8 (+ 6 (- 4 2)))
                (/ 8 (+ (- 6 4) 2))
                (/ (+ 8 6) (- 4 2))
                (/ (+ 8 (- 6 4)) 2)
                (/ (+ (- 8 6) 4) 2)))

; [List-of Tree] [List-of Symbol] [Lis-of Number] -> [List-of Tree]
; convert a tree structure to a BET by mapping all nodes and leaves
(define (map-all-trees tree-structure operations numbers)
  (local
    (; Tree [List-of Symbol] [Lis-of Number] -> Tree
     ; map nodes and trees for the tree
     (define (map-tree tree o n)
       (map-leaves (map-nodes tree o) n)))
    (map (λ (t) (map-tree t operations numbers)) tree-structure)))

; Tree [List-of Symbol] -> Tree
; maps all nodes in tree with new-nodes from left to right
(define (map-nodes tree new-nodes)
  (local
    (; Tree -> Boolean
     ; does t have a numerical node?
     (define (num-as-node? t)
       (and (not (symbol? t))
            (or (number? (first t))
                (num-as-node? (second t))
                (num-as-node? (third t)))))
     ; Tree Symbol -> Tree
     ; replaces left-most node in t with s
     (define (replace-node t s)
       (match t
         ['empty t]
         [(list n l r)
          (cond [(number? n) (list s l r)]
                [else (if (num-as-node? l)
                          (list n (replace-node l s) r)
                          (list n l (replace-node r s)))])]))
     ; Tree [List-of Symbol] -> Tree
     ; replaces nodes till all elems in l are placed in t
     (define (replace-all-nodes t l)
       (match l
         ['() t]
         [(cons f r) (replace-all-nodes (replace-node t f) r)])))
    (replace-all-nodes tree new-nodes)))

; Tree [List-of Number] -> Tree
; maps all leaves in tree with new-leaves from left to right
(define (map-leaves tree new-leaves)
  (local
    (; Tree [List-of Number] -> Tree
     ; replace all leafs in t with l from left to right
     (define (replace-all-leaf t l)
       (match l
         ['() t]
         [(cons f r) (replace-all-leaf (replace-leaf t f) r)]))
     ; Tree -> Boolean
     ; does tree have 'empty as a leaf in it?
     (define (empty-in-tree? t)
       (match t
         [(? symbol?) (symbol=? t 'empty)]
         [(? number?) #false]
         [(list n l r)
          (or (and (symbol? l) (symbol=? 'empty l))
              (and (symbol? r) (symbol=? 'empty r))
              (empty-in-tree? l)
              (empty-in-tree? r))]))
     ; Tree Number -> Tree
     ; replace the left-most 'empty leaf in t with n
     (define (replace-leaf t node)
       (match t
         ['empty node]
         [(list n l r)
          (if (empty-in-tree? l)
              (list n (replace-leaf l node) r)
              (list n l (replace-leaf r node)))])))
    (replace-all-leaf tree new-leaves)))